BriefGPT.xyz
Aug, 2018
通过马尔可夫链浓度推导强化学习的遗憾界
Regret Bounds for Reinforcement Learning via Markov Chain Concentration
HTML
PDF
Ronald Ortner
TL;DR
针对有 $S$ 个状态、$A$ 个行动、混合时间参数 $t_{mix}$ 的均匀遍历马尔可夫决策过程，在简单的乐观算法下，$T$ 步后 $\tilde{O}(\sqrt{t_{mix}SAT})$ 的遗憾度可推导出，这些界限是所有给定参数的最优依赖关系下，普遍的非情节性问题的首个遗憾度界限；唯一可以改善它们的方法是使用可选的混合时间参数。
Abstract
We give a simple
optimistic algorithm
for which it is easy to derive
regret bounds
of $\tilde{O}(\sqrt{t_{\rm mix} SAT})$ after $T$ steps in uniformly
→