强化学习与入场控制的懊悔界限

Jun, 2024

Reinforcement Learning and Regret Bounds for Admission Control

Lucas Weber, Ana Bušić, Jiamin Zhu

TL;DR任何强化学习算法的期望遗憾在无折扣回报情况下下界为 $\Omega\left (\sqrt {DXAT}\right)$，其中 $D$ 表示马尔科夫决策过程的直径，$X$ 表示状态空间的大小，$A$ 表示动作空间的大小，$T$ 表示时间步数。然而，这个下界是一般性的，考虑到问题结构的一些具体知识可以获得更小的遗憾。在本文中，我们考虑了一个具有 $m$ 个作业类和类依赖奖励和持有成本的 $M/M/c/S$ 队列的入场控制问题。排队系统的直径通常是缓冲区大小 $S$ 的指数级，这使得先前的下界在实际使用中变得困难。我们提出了一种受 UCRL2 启发的算法，并利用问题结构来上界有限服务器情况下的期望总遗憾为 $O (S\log T + \sqrt {mT \log T})$。在无限服务器情况下，我们证明了遗憾对 $S$ 的依赖性消失。

Abstract

The expected regret of any reinforcement learning algorithm is lower bounded by $\Omega\left(\sqrt{DXAT}\right)$ for undiscounted returns, where $D$ is the diameter of the Markov decision process, $X$ the size of

reinforcement learning expected regret admission control problem $m/m/c/s$ queue ucrl2 algorithm

发现论文，激发创造

通过马尔可夫链浓度推导强化学习的遗憾界

针对有 $S$ 个状态、$A$ 个行动、混合时间参数 $t_{mix}$ 的均匀遍历马尔可夫决策过程，在简单的乐观算法下，$T$ 步后 $\tilde {O}(\sqrt {t_{mix} SAT})$ 的遗憾度可推导出，这些界限是所有给定参数的最优依赖关系下，普遍的非情节性问题的首个遗憾度界限；唯一可以改善它们的方法是使用可选的混合时间参数。

Aug, 2018

部分可观察排队网络中的最优入场控制学习

我们提出了一种高效的强化学习算法，用于在部分可观察排队网络中学习最佳的入场控制策略，其中部分可观察性是指只有网络的到达和离开时间是可观察的，最优性是指在无限时间内的平均持有 / 拒绝成本。

Aug, 2023

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

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

Dec, 2021

强化学习的极小后悔界

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

Mar, 2017

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

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

Mar, 2014

强化学习的后验采样：最坏情况的遗憾界

提出了一种基于后验采样的算法，应用于具有有限但未知直径的 Markov 决策过程中，证明了近最优的最坏情况遗憾上界。这种方法通过证明 Dirichlet 分布的反集中性，可能具有独立研究价值，并将总奖励与最优无限时维度折扣的平均奖励策略的总期望奖励在时间结构 $T$ 中呈现出紧密的匹配。

May, 2017

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

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

Mar, 2018

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

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

May, 2019

无折扣连续强化学习的在线遗憾界

该研究针对连续状态空间中的无折扣强化学习问题，提出了一种结合状态聚合和使用置信上界实现面对不确定性乐观的算法，在 rewards 和 transition probabilities 保持 Holder 连续性的情况下，给出了子线性遗憾界。

Feb, 2013

多智能体多臂赌博机中的遗憾下界

在多臂赌博机领域，多智能体多臂赌博机方法已经受到了广泛关注，但对应的遗憾下界的研究相对较少。本文在不同情景下首次全面研究了遗憾下界，并证明了它们的紧密性。当图表现出良好的连通性和奖励是随机分布时，我们证明了实例相关上界的 O（log T）下界和平均差值独立上界的 sqrt（T）下界。在对抗奖励的假设下，我们建立了连接图的 O（T^（2/3））下界，从而弥合了以前工作中下界与上界之间的差距。当图表现为不连通时，我们还展示了线性的遗憾下界。与以前的研究相比，本文全面研究了这些情景下的紧密下界。

Aug, 2023