用后验采样改进Q-learning，理论性能逼近最优。
Q-learning with Posterior Sampling
- 基于高斯后验采样设计探索机制，类比多臂赌博机的汤普森采样。
- 在表格型马尔可夫决策过程下，达到近似最优的遗憾上界 $\tilde O(H^2\sqrt{SAT})$。
- 为后验采样与强化学习结合提供新思路，适合研究理论强化学习者。
贝叶斯后验采样在许多探索-利用场景中表现出色，但其理论分析仍具挑战性，尤其在复杂强化学习环境中。本文提出一种基于Q-learning的后验采样算法——PSQL，通过在Q值上使用高斯后验进行探索，类比多臂赌博机中的经典汤普森采样。在表格型周期性马尔可夫决策过程（episodic MDP）设定下，PSQL实现了 $ ilde O(H^2 oot{2}{SAT})$ 的遗憾上界，接近已知的 $Ω(H\root{2}{SAT})$ 下界。其中，S、A 分别为状态数和动作数，$T=KH$，K为总回合数，H为规划时长。本工作揭示了将后验采样与动态规划及基于TD-learning的强化学习算法结合的核心难点，并提出创新解法，为未来分析更复杂强化学习场景中的该技术奠定基础。
原文摘要 · Abstract (English)
Bayesian posterior sampling techniques have demonstrated superior empirical performance in many exploration-exploitation settings. However, their theoretical analysis remains a challenge, especially in complex settings like reinforcement learning. In this paper, we introduce Q-Learning with Posterior Sampling (PSQL), a simple Q-learning-based algorithm that uses Gaussian posteriors on Q-values for exploration, akin to the popular Thompson Sampling algorithm in the multi-armed bandit setting. We show that in the tabular episodic MDP setting, PSQL achieves a regret bound of $\tilde O(H^2\sqrt{SAT})$, closely matching the known lower bound of $Ω(H\sqrt{SAT})$. Here, S, A denote the number of states and actions in the underlying Markov Decision Process (MDP), and $T=KH$ with $K$ being the number of episodes and $H$ being the planning horizon. Our work provides several new technical insights into the core challenges in combining posterior sampling with dynamic programming and TD-learning-based RL algorithms, along with novel ideas for resolving those difficulties. We hope this will form a starting point for analyzing this efficient and important algorithmic technique in even more complex RL settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。