近期一些研究工作展示了强化学习中降低后悔的边界可以(几乎)与计划周期无关,即所谓的无周期边界。然而,这些后悔边界仅适用于允许对转移模型大小多项式依赖的设置,例如表格型马尔科夫决策过程(MDP)和线性混合 MDP。我们给出了流行的线性 MDP 设置的首个无周期边界,其中转移模型的大小可以是指数级大甚至是不可数的。与先前的工作相比,该方法不需要明确估计转移模型并计算不同时间步的非齐次值函数,而是直接估计值函数和置信区间集合。通过保持多个加权最小二乘估计器,该方法获得了无周期边界,并且通过结构引理证明了非齐次值函数的最大总变差受特征维数的多项式因子限制。
Mar, 2024
本文利用离线强化学习技术研究了时域同质马尔可夫决策过程上的策略评估和优化问题,并提出了一种递归方法来限制离线场景下的 “总方差” 项,得到了近似无视野远的样本复杂度上限。
Mar, 2021
本文通过提出第一个无界时间步长多次对抗强化学习的策略搜索算法,使用方差 - 不确定性感知加权最小二乘估计器和基于占用度量的在线搜索技术,以解决探索和对抗性奖励所带来的挑战,证明算法在全信息反馈下具有 O ((d+log (|S|^2|A|)) sqrt (K)) 的后悔界,其中 d 是未知转移核线性参数化的已知特征映射的维数,K 是剧集数量,|S| 和 |A| 是状态和行为空间的基数。
May, 2023
本文研究基于后知的上下文中的潜在马尔可夫决策过程(LMDPs)的强化学习中的遗憾最小化问题,设计了一种新的基于模型的算法框架,证明了具有一定时间复杂度的遗憾上限。
Oct, 2022
该研究论文提出了第一个计算高效、无横向界限算法,其中采用了加权最小二乘法,以用于未知状态转移动态的估算,并能够应用于异构线性 bandits 中,达到了比已知算法更优的效果。
May, 2022
在稀疏线性马尔可夫决策过程中,通过引入一种新的算法 - Lasso fitted Q-iteration, 通过一个具有一定条件的数据策略,以几乎无维度代价实现对在线强化学习的降低,但线性后悔在常用政策情况下仍然无法避免。
Nov, 2020
设计了一个计算有效的算法,通过将平均奖励设定近似为折扣设定,并且在适当调整贴现因子时,通过运行基于乐观值迭代的算法来实现无限时段平均奖励线性马尔可夫决策过程 (MDP) 的 O (sqrt (T)) 的遗憾。
May, 2024
本文聚焦在有限状态有限时间的马尔科夫决策过程设置下的模型基 RL,证明了探索具有贪心策略可以实现紧密的极小极大性能,从而完全避免使用 full-planning,而复杂度降为 S,并通过实时动态规划进行了新颖的分析。
May, 2019
本文研究了无限时间段平均回报马尔可夫决策过程(MDP)。与现有研究不同的是,我们采用了基于通用策略梯度的算法,使其摆脱了线性 MDP 结构的约束。我们提出了一种基于策略梯度的算法,并证明了其全局收敛性质。然后我们证明该算法具有 $\tilde {\mathcal {O}}({T}^{3/4})$ 的后悔度。值得注意的是,本文是第一次对于一般参数化策略梯度算法在平均回报情景下的后悔计算进行了探索性研究。
Sep, 2023
本文提出两种基于无模型的强化学习算法,用于学习无限时间持续的平均回报 MDP 问题,第一种算法在弱相互通信的 MDPs 中,将问题简化为折扣回报问题,在 T 步之后的遗憾为 O (T^(2/3)), 该算法是解决该问题的第一种无模型的算法;第二种算法利用了对抗多臂老虎机自适应算法的最新进展,将遗憾进一步改进至 O (sqrt (T)),但需要更强的符合人类定义的遍历条件。这个结果取代了 Abbasi-Yadkori 等人 2019 年只有在符合人类定义的遍历条件下的 ergodic MDP 才能达到 O (T^(3/4)) 的遗憾。
Oct, 2019