通过评估最优偏置函数实现强化学习的遗憾最小化

Jun, 2019

通过评估最优偏置函数实现强化学习的遗憾最小化

Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Zihan Zhang, Xiangyang Ji

TL;DR基于 “面对不确定性的乐观原则” 的算法，使用有限状态 - 动作空间的、用马尔可夫决策过程（MDP）建模的强化学习（RL）有效学习。通过评估最佳偏置函数 $h^{*}$ 的状态对差异，该算法在已知 $sp (h^{*})$ 的情况下实现 MDP 的遗憾界为 $\tilde {O}(\sqrt {SAHT})$，这个结果超过了先前的最佳遗憾界 $\tilde {O}(S\sqrt {AHT})$，并且匹配了遗憾下界。此外，对于有限直径 $D$ 的 MDP，我们证明了 $ ilde {O}(\sqrt {SADT})$ 接近于最佳遗憾上界。

Abstract

We present an algorithm based on the \emph{Optimism in the Face of Uncertainty} (OFU) principle which is able to learn reinforcement learning (RL) modeled by markov decision process (MDP) with →

reinforcement learning markov decision process regret bound optimism in the face of uncertainty finite state-action space

发现论文，激发创造

MDP 中无折扣强化学习的方差感知遗憾界

本研究考虑了在未知的离散马尔科夫决策过程下，使用平均奖励准则的强化学习问题，其中学习者从一个初始状态开始，通过单个观察流与系统进行交互。我们提供了 KL-UCRL 算法的新分析，为该算法建立了高概率遗憾界，对于同一类随机过程的效果较之前的算法遗憾界有数量级的提升。

Mar, 2018

强化学习的极小后悔界

本文研究了有限时间 MDPs 中探索的最优性问题，提出了一种基于值迭代的乐观算法，其探索奖励基于下一个状态的经验值的变化量，通过使用集中不等式提高算法的可伸缩性，取得了优于先前最佳算法的研究成果，可以实现与已知理论下限相匹配的后悔度。

Mar, 2017

在平均回报 MDPs 中实现可行的最小最优后悔

这篇论文介绍了一种具有最小最大后悔度的可行算法，该算法通过使用一种新颖的子程序，即 Projected Mitigated Extended Value Iteration（PMEVI），来高效地计算偏差受限最优策略。同时，该算法不需要先前关于偏差函数的信息。

Jun, 2024

用最优后悔学习在度量空间中控制

探讨了针对具有任意状态和动作空间的有限时间确定性控制系统的在线强化学习问题，提出了一种基于上置信强化学习的 Q 函数的乐观估计算法，证明了算法的性能界限和下界。

May, 2019

分解马尔可夫决策过程中近最优强化学习

通过采用 posterior sampling reinforcement learning (PSRL) 算法和 upper confidence bound algorithm (UCRL-Factored) 算法，在已知为 factored MDP 系统中，可将 regret 值多项式缩小到编码所需的 factored MDP 参数数量级别，从而大大减少了学习时间。

Mar, 2014

利用线性函数近似的强化学习的一阶遗憾：一种鲁棒估计方法

本研究基于鲁棒 Catoni 平均值估计器，提出一种新的鲁棒自归一化浓度界，解决了已有技术在大状态空间强化学习中无法获得遗憾上界的问题，并证明了在线性 MDP 设定下，可以获得与最优策略性能某种度量成比例的遗憾上界。

Dec, 2021

线性函数逼近的对抗式 MDP 的精炼遗憾

本文研究了在损失函数任意的情况下，对于线性近似的 Q 函数，提出了两种算法，可以在拥有模拟器的情况下使得损失最小值达到 $\tilde {\mathcal O}(\sqrt K)$，并在无模拟器情况下实现了 $ ilde {\mathcal O}(K^{8/9})$ 的表现，改进了之前的表现

Jan, 2023

基于模型的强化学习中贪心策略的严格遗憾界

本文聚焦在有限状态有限时间的马尔科夫决策过程设置下的模型基 RL，证明了探索具有贪心策略可以实现紧密的极小极大性能，从而完全避免使用 full-planning，而复杂度降为 S，并通过实时动态规划进行了新颖的分析。

May, 2019

$\sqrt {n}$-Regret 算法在带有函数逼近和低 Bellman 等级的马尔可夫决策过程学习中的应用

本文提出了一种在线学习算法，即 Adaptive Value-function Elimination（AVE），用于大规模状态空间下的 Markov 决策过程（MDPs），形式化了 OLIVE 中的淘汰步骤为上下文乐队问题，从而在学习过程中实现了最优价值函数的学习和非常低的累积遗憾，这是首次在具有一般价值函数逼近的随机 MDPs 中以 Θ（√n）的累积遗憾结果呈现出增强学习。

Sep, 2019

近乎最小最大化优化强化学习在折扣 MDPs 上

通过乐观不确定性原则和伯恩斯坦型奖励设计的算法 UCBVI-γ，最小化为折扣 MDPs 所得出的代价，其误差上界是 sqrt (SAT)/(1−γ)^(3/2)，与 minimax 下界的误差相等。

Oct, 2020