强化学习的极小后悔界
本研究讨论了有限时间内强化学习中的探索和开发困境,并引入了基于乐观初始化的随机最小二乘值迭代算法来解决维度过大或连续状态下的情况。该算法的频率上界误差为 O (d^2 H^2 sqrt (T)),为带有函数逼近的随机探索的首次频率后悔分析。
Nov, 2019
本研究基于鲁棒 Catoni 平均值估计器,提出一种新的鲁棒自归一化浓度界,解决了已有技术在大状态空间强化学习中无法获得遗憾上界的问题,并证明了在线性 MDP 设定下,可以获得与最优策略性能某种度量成比例的遗憾上界。
Dec, 2021
针对有 $S$ 个状态、$A$ 个行动、混合时间参数 $t_{mix}$ 的均匀遍历马尔可夫决策过程,在简单的乐观算法下,$T$ 步后 $\tilde {O}(\sqrt {t_{mix} SAT})$ 的遗憾度可推导出,这些界限是所有给定参数的最优依赖关系下,普遍的非情节性问题的首个遗憾度界限;唯一可以改善它们的方法是使用可选的混合时间参数。
Aug, 2018
基于 “面对不确定性的乐观原则” 的算法,使用有限状态 - 动作空间的、用马尔可夫决策过程(MDP)建模的强化学习(RL)有效学习。通过评估最佳偏置函数 $h^{*}$ 的状态对差异,该算法在已知 $sp (h^{*})$ 的情况下实现 MDP 的遗憾界为 $\tilde {O}(\sqrt {SAHT})$,这个结果超过了先前的最佳遗憾界 $\tilde {O}(S\sqrt {AHT})$,并且匹配了遗憾下界。此外,对于有限直径 $D$ 的 MDP,我们证明了 $ ilde {O}(\sqrt {SADT})$ 接近于最佳遗憾上界。
Jun, 2019
通过引入方差缩减策略,设计了一个记忆高效的算法来解决在线序列化强化学习中的勘探和开发之间的平衡问题,该算法的空间复杂度为 $ O (SAH)$,较以前的算法提高了 $S^5A^3$ 倍的效率。
Oct, 2021
这篇论文介绍了一种具有最小最大后悔度的可行算法,该算法通过使用一种新颖的子程序,即 Projected Mitigated Extended Value Iteration(PMEVI),来高效地计算偏差受限最优策略。同时,该算法不需要先前关于偏差函数的信息。
Jun, 2024
研究在强化学习中使用随机值函数来最小化遗憾。提出了随机最小二乘值迭代算法的夹剪变体,其在有限时间节点的马尔科夫决策过程中获得了较好的遗憾上限,并且与现有基于 Thompson Sampling 的遗憾上限的表现持平。
Oct, 2020
设计了一个计算有效的算法,通过将平均奖励设定近似为折扣设定,并且在适当调整贴现因子时,通过运行基于乐观值迭代的算法来实现无限时段平均奖励线性马尔可夫决策过程 (MDP) 的 O (sqrt (T)) 的遗憾。
May, 2024
本文聚焦在有限状态有限时间的马尔科夫决策过程设置下的模型基 RL,证明了探索具有贪心策略可以实现紧密的极小极大性能,从而完全避免使用 full-planning,而复杂度降为 S,并通过实时动态规划进行了新颖的分析。
May, 2019
通过采用 posterior sampling reinforcement learning (PSRL) 算法和 upper confidence bound algorithm (UCRL-Factored) 算法,在已知为 factored MDP 系统中,可将 regret 值多项式缩小到编码所需的 factored MDP 参数数量级别,从而大大减少了学习时间。
Mar, 2014