基于无界时间跨度和方差的隐含马尔可夫决策过程强化学习
近期一些研究工作展示了强化学习中降低后悔的边界可以(几乎)与计划周期无关,即所谓的无周期边界。然而,这些后悔边界仅适用于允许对转移模型大小多项式依赖的设置,例如表格型马尔科夫决策过程(MDP)和线性混合 MDP。我们给出了流行的线性 MDP 设置的首个无周期边界,其中转移模型的大小可以是指数级大甚至是不可数的。与先前的工作相比,该方法不需要明确估计转移模型并计算不同时间步的非齐次值函数,而是直接估计值函数和置信区间集合。通过保持多个加权最小二乘估计器,该方法获得了无周期边界,并且通过结构引理证明了非齐次值函数的最大总变差受特征维数的多项式因子限制。
Mar, 2024
本篇论文研究在线学习中的方差自适应算法,提出了适用于线性赌臂机以及线性混合马尔可夫决策过程的遗憾界分析,该方法在未知方差的情况下,能够实现 Regret 的拟多项式算法复杂度降低。
Nov, 2021
本文通过提出第一个无界时间步长多次对抗强化学习的策略搜索算法,使用方差 - 不确定性感知加权最小二乘估计器和基于占用度量的在线搜索技术,以解决探索和对抗性奖励所带来的挑战,证明算法在全信息反馈下具有 O ((d+log (|S|^2|A|)) sqrt (K)) 的后悔界,其中 d 是未知转移核线性参数化的已知特征映射的维数,K 是剧集数量,|S| 和 |A| 是状态和行为空间的基数。
May, 2023
该研究论文提出了第一个计算高效、无横向界限算法,其中采用了加权最小二乘法,以用于未知状态转移动态的估算,并能够应用于异构线性 bandits 中,达到了比已知算法更优的效果。
May, 2022
本研究考虑了在未知的离散马尔科夫决策过程下,使用平均奖励准则的强化学习问题,其中学习者从一个初始状态开始,通过单个观察流与系统进行交互。我们提供了 KL-UCRL 算法的新分析,为该算法建立了高概率遗憾界,对于同一类随机过程的效果较之前的算法遗憾界有数量级的提升。
Mar, 2018
在稀疏线性马尔可夫决策过程中,通过引入一种新的算法 - Lasso fitted Q-iteration, 通过一个具有一定条件的数据策略,以几乎无维度代价实现对在线强化学习的降低,但线性后悔在常用政策情况下仍然无法避免。
Nov, 2020
该研究针对马尔可夫决策过程中的无折扣强化学习问题提出了一种算法,并提供了针对最优非静态策略的性能保证。给出了在 MDP 总变差方面的差错的上限,这是一般强化学习设置的第一个变分差错界限。
May, 2019
本研究提出了一种政策优化算法,用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题,该算法在符合一定条件的 MDP 下具有较低的后悔度和约束违反率,并将其推广到弱通信 MDP 领域,为该领域提供了复杂度可行的算法。
Jan, 2022
设计了一个计算有效的算法,通过将平均奖励设定近似为折扣设定,并且在适当调整贴现因子时,通过运行基于乐观值迭代的算法来实现无限时段平均奖励线性马尔可夫决策过程 (MDP) 的 O (sqrt (T)) 的遗憾。
May, 2024