方差缩减 $Q$- 学习达到了最小极差优化

Jun, 2019

方差缩减 $Q$- 学习达到了最小极差优化

Variance-reduced $Q$-learning is minimax optimal

Martin J. Wainwright

TL;DR介绍和分析了一种方差减少的 Q-learning 方法，为具有有限状态和动作空间的折扣 MDPs 提供了相对精确的最优 Q 函数估计，其采样数量与最小极值下界匹配。

Abstract

We introduce and analyze a form of variance-reduced $Q$-learning. For $\gamma$-discounted mdps with finite state space $\mathcal{X}$ and action space $\mathcal{U}$, we prove that it yields an $\epsilon$-accurate estimat

variance-reduced q-learning discounted mdps accurate estimate optimal q-function minimax lower bounds

发现论文，激发创造

最优值估计中的实例最优性：通过方差缩减 Q 学习实现自适应

本文提出一个本地极小极大方法，分析了计算强化学习下的最优 $Q$ 值函数的实例特定行为，并提供一个针对 $Q$ 学习中困难问题和易解问题的有力解释。

Jun, 2021

Q-Learning 算法是否达到 Minimax 最优性？一种紧凑的样本复杂度分析

本文研究 Q-learning 同步和异步情况下的样本复杂性和子优秀性，并展示在异步情况下的样本复杂性更强，Q-learning 算法是严格亚最优的。

Feb, 2021

方差减少的分布鲁棒 Q 学习的样本复杂性

本论文提出了两种模型无关的算法，分别是分布鲁棒的 Q-learning 及其方差缩减的版本。这些算法可在处理分布移位时有效地学习强大的策略。在一系列数值实验中，这些算法的理论发现和效率得到了证实。

May, 2023

异步 Q 学习的样本复杂度：更精确的分析和降低方差

该研究通过异步 Q-learning 算法，在马尔科夫决策流程中的样本轨迹中学习最优动作价值函数，给出了基于 L∞的样本复杂度分析及等式组，并在此基础上提出一种新的方差缩减技术，进一步提高了算法的效率。

Jun, 2020

最近邻 Q 学习

该论文研究利用最近邻回归方法的最近邻 Q 学习算法，从单一样本路径中学习具有连续状态空间和未知转移核的无限期贴现 MDPs 的最优 Q 函数，提供了紧密的有限样本收敛速率分析和样本复杂度。

Feb, 2018

降低方差的价值迭代算法及用于求解马尔可夫决策流程的更快速算法

提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解，并证明了算法的收敛性和复杂度。同时，结合经典的价值迭代与方差约减技术，改进了该算法的性能，使其具有线性收敛性和渐进最优性。

Oct, 2017

通用效用的强化学习：更简单的方差缩减和大状态行动空间

我们提出了一种更简单的单循环，无参数归一化策略梯度算法，用于解决具有一般效用的强化学习问题，其中包括约束强化学习，纯探索以及从演示中学习等问题，同时通过线性函数逼近解决大状态 - 动作空间的设置，并展示了简单的策略梯度法的样本复杂度。

Jun, 2023

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

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

Mar, 2018

最小化差值的最优 $Q$ 学习与最近邻

该研究提出两种新的 Q 学习方法，以弥补 (Shah and Xie, 2018) 中收敛速率差异，其中一种是脱机方法，另一种是在线方法。尽管我们仍然使用最近邻方法估计 Q 函数，但算法与 (Shah and Xie, 2018) 有着关键的不同之处。特别地，在离散区域中，我们将核最近邻方法替换为直接最近邻方法。因此，我们的方法显著提高了收敛速率。此外，在高维状态空间中，时间复杂度也显著改善。我们的分析表明，脱机和在线方法都是极小极大速率最优的。

Aug, 2023

基于规约的平均回报 MDP 的近似最优策略学习

本研究考虑采用生成模型（模拟器）以获取平均奖励 MDP 中的 eps 策略最优性的样本复杂度。

Dec, 2022