首个证明上下文博弈策略优化可达到最优后悔上界的方法。
Optimal Regret for Policy Optimization in Contextual Bandits
- 基于离线函数逼近的策略优化算法，实现高概率最优后悔上界。
- 在 $K$ 轮中，后悔上界为 $ ilde{O}( oot{2}{K| extcal{A}| extlog| extcal{F}|})$。
- 理论与实证结合，适合关注上下文强化学习理论的读者。
我们首次为应用于随机上下文多臂老虎机（CMAB）问题的策略优化技术，提供了高概率最优后悔上界，该问题采用通用离线函数逼近。我们的算法高效且达到最优后悔上界 $ ilde{O}( oot{2}{K| extcal{A}| extlog| extcal{F}|})$，其中 $K$ 为轮次数，$ extcal{A}$ 为动作集，$ extcal{F}$ 为用于近似损失的函数类。结果弥合了理论与实践的差距，证明了广泛使用的上下文博弈策略优化方法可实现严格证明的最优后悔上界。我们通过实验评估验证了理论结果。
原文摘要 · Abstract (English)
We present the first high-probability optimal regret bound for a policy optimization technique applied to the problem of stochastic contextual multi-armed bandit (CMAB) with general offline function approximation. Our algorithm is both efficient and achieves an optimal regret bound of $\widetilde{O}(\sqrt{ K|\mathcal{A}|\log|\mathcal{F}|})$, where $K$ is the number of rounds, $\mathcal{A}$ is the set of arms, and $\mathcal{F}$ is the function class used to approximate the losses. Our results bridge the gap between theory and practice, demonstrating that the widely used policy optimization methods for the contextual bandit problem can achieve a rigorously-proved optimal regret bound. We support our theoretical results with an empirical evaluation of our algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。