基于模型的强化学习中贪心策略的严格遗憾界
本研究基于鲁棒 Catoni 平均值估计器,提出一种新的鲁棒自归一化浓度界,解决了已有技术在大状态空间强化学习中无法获得遗憾上界的问题,并证明了在线性 MDP 设定下,可以获得与最优策略性能某种度量成比例的遗憾上界。
Dec, 2021
本文研究了有限时间 MDPs 中探索的最优性问题,提出了一种基于值迭代的乐观算法,其探索奖励基于下一个状态的经验值的变化量,通过使用集中不等式提高算法的可伸缩性,取得了优于先前最佳算法的研究成果,可以实现与已知理论下限相匹配的后悔度。
Mar, 2017
通过引入方差缩减策略,设计了一个记忆高效的算法来解决在线序列化强化学习中的勘探和开发之间的平衡问题,该算法的空间复杂度为 $ O (SAH)$,较以前的算法提高了 $S^5A^3$ 倍的效率。
Oct, 2021
通过采用 posterior sampling reinforcement learning (PSRL) 算法和 upper confidence bound algorithm (UCRL-Factored) 算法,在已知为 factored MDP 系统中,可将 regret 值多项式缩小到编码所需的 factored MDP 参数数量级别,从而大大减少了学习时间。
Mar, 2014
基于 “面对不确定性的乐观原则” 的算法,使用有限状态 - 动作空间的、用马尔可夫决策过程(MDP)建模的强化学习(RL)有效学习。通过评估最佳偏置函数 $h^{*}$ 的状态对差异,该算法在已知 $sp (h^{*})$ 的情况下实现 MDP 的遗憾界为 $\tilde {O}(\sqrt {SAHT})$,这个结果超过了先前的最佳遗憾界 $\tilde {O}(S\sqrt {AHT})$,并且匹配了遗憾下界。此外,对于有限直径 $D$ 的 MDP,我们证明了 $ ilde {O}(\sqrt {SADT})$ 接近于最佳遗憾上界。
Jun, 2019
本文介绍了一种基于加权线性回归方案的计算有效算法,用于处理线性马尔可夫决策过程的强化学习问题。该算法实现了近似最小化最优遗憾,具有较好的效率,对参数化转换动态有良好的适应性,可以对研究领域进行更细致的探讨。
Dec, 2022
近期一些研究工作展示了强化学习中降低后悔的边界可以(几乎)与计划周期无关,即所谓的无周期边界。然而,这些后悔边界仅适用于允许对转移模型大小多项式依赖的设置,例如表格型马尔科夫决策过程(MDP)和线性混合 MDP。我们给出了流行的线性 MDP 设置的首个无周期边界,其中转移模型的大小可以是指数级大甚至是不可数的。与先前的工作相比,该方法不需要明确估计转移模型并计算不同时间步的非齐次值函数,而是直接估计值函数和置信区间集合。通过保持多个加权最小二乘估计器,该方法获得了无周期边界,并且通过结构引理证明了非齐次值函数的最大总变差受特征维数的多项式因子限制。
Mar, 2024
本文研究基于后知的上下文中的潜在马尔可夫决策过程(LMDPs)的强化学习中的遗憾最小化问题,设计了一种新的基于模型的算法框架,证明了具有一定时间复杂度的遗憾上限。
Oct, 2022
本文提出了一种强化学习与策略建议(RLPA)算法,可以利用提供的一组输入策略并学会使用最佳策略来解决当前的强化学习任务。我们证明了算法的深度复杂度和次线性遗憾与最佳输入策略相对应,而这种遗憾和复杂度与状态和动作空间的大小无关。我们的实验模拟支持我们的理论分析。这表明 RLPA 可能在提供先前良好策略的大型领域中具有重要优势。
May, 2013