首个方差感知细粒度间隙界，UCB-Bernstein+刷新最优切换成本！
Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning
📖 AI 总结
本文研究情节式表格马尔可夫决策过程下的无模型在线强化学习，同时关注依赖间隙的遗憾界与策略切换成本。此前，基于Hoeffding型探索奖励的无模型算法已建立细粒度间隙依赖分析，但采用方差型探索奖励的算法虽在最坏情形和粗粒度间隙依赖保证上更优，其细粒度间隙依赖结果仍属空白。本文针对改进算法UCB-Bernstein+，首次给出方差感知无模型在线强化学习的细粒度间隙依赖遗憾上界，并通过引入分阶段策略更新设计与精细方差奖励，取得目前最优的间隙依赖局部切换成本。分析还表明，该算法在遗憾和局部切换成本两方面均改进了原始UCB-Bernstein的最坏情形保证，数值实验也验证了其良好表现。
🔑 关键词速览
| 无模型在线强化学习 | 一种不依赖环境模型、直接通过与环境的交互来学习最优策略的强化学习方法。 |
| 分幕式表格马尔可夫决策过程 | 状态和动作空间有限且以表格形式表示，学习过程分为多个独立幕的马尔可夫决策过程。 |
| 依赖间隙的遗憾 | 遗憾上界与最优动作与次优动作之间的差距（间隙）相关的性能度量。 |
| 策略切换成本 | 在在线学习过程中，因策略更新而导致的额外开销或代价。 |
| UCB-Bernstein+ | 一种改进的UCB-Bernstein算法，利用基于方差的探索奖励，在遗憾和切换成本上具有更优的理论保证。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅