新算法π₀-PSRL破解探索时机难题，遗憾界逼近理论下界！
Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
📖 AI 总结
该论文研究有限时域情景式马尔可夫决策过程（MDP）中的遗憾最小化问题。现有算法虽已实现极小极大最优，但实例依赖最优性仍缺乏可计算的方法。作者提出π₀-PSRL，一种后验采样强化学习（PSRL）的变体：当采样MDP与经验MDP的最优策略不一致时触发探索，并在探索回合中遵循固定参考策略π₀，从而将“是否探索”的判断与“如何探索”的策略选择解耦，克服了标准PSRL中采样最优策略未必适合探索的缺陷。作者证明了π₀-PSRL的实例依赖遗憾界，识别出π₀带来的对数级探索成本，向匹配情景式强化学习的渐近下界迈进一步。证明中还提出了推导问题依赖遗憾界的新证明结构及Dirichlet随机变量的集中结果，可能具有独立价值。
🔑 关键词速览
| Episodic MDPs | 分段马尔可夫决策过程，一种具有有限时域和重复回合的强化学习框架。 |
| PSRL | 后验采样强化学习，一种基于贝叶斯后验采样的探索算法。 |
| Instance-dependent regret | 实例依赖遗憾，衡量算法在特定问题实例上的累积损失，通常比极小极大遗憾更精细。 |
| Reference policy π0 | 参考策略π0，在探索回合中使用的固定策略，用于解耦探索决策与策略选择。 |
| Dirichlet random variables | 狄利克雷随机变量，常用于表示概率分布上的不确定性，在贝叶斯方法中作为共轭先验。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅