使用线性函数逼近学习无限时间平均回报马尔可夫决策过程
设计了一个计算有效的算法,通过将平均奖励设定近似为折扣设定,并且在适当调整贴现因子时,通过运行基于乐观值迭代的算法来实现无限时段平均奖励线性马尔可夫决策过程 (MDP) 的 O (sqrt (T)) 的遗憾。
May, 2024
我们研究了具有非线性函数逼近的基于模型的强化学习,其中底层马尔可夫决策过程(MDP)的转移函数由一个多项式逻辑模型给出。本文针对无限时间平均奖励设定,提出了两种算法。第一个算法 UCRL2-MNL 适用于通信 MDP 类,并实现了一种具有 (近似)Ο(dD√T) 的遗憾保证,其中 d 是特征映射的维数,D 是底层 MDP 的直径,T 是时间界。第二个算法 OVIFH-MNL 在计算上更有效,并适用于更一般的弱通信 MDP 类,我们展示了其具有 (近似)Ο(d^(2/5) sp (v^*) T^(4/5)) 的遗憾保证,其中 sp (v^*) 是相关最优偏差函数的散度。我们还证明了对于最大直径为 D 的可通信 MDP,学习具有 MNL 转移的复杂度的 Ω(d√(DT)) 的下界。此外,我们对于具有 MNL 函数逼近的 H - 时间界的情况,展示了 Ω(dH^(3/2)√K) 的遗憾下界,在这里 K 是序列的数量,该下界优于有限时间界设定的已知最佳下界。
Jun, 2024
本文研究了在损失函数任意的情况下,对于线性近似的 Q 函数,提出了两种算法,可以在拥有模拟器的情况下使得损失最小值达到 $\tilde {\mathcal O}(\sqrt K)$,并在无模拟器情况下实现了 $ ilde {\mathcal O}(K^{8/9})$ 的表现,改进了之前的表现
Jan, 2023
本文介绍了一种基于加权线性回归方案的计算有效算法,用于处理线性马尔可夫决策过程的强化学习问题。该算法实现了近似最小化最优遗憾,具有较好的效率,对参数化转换动态有良好的适应性,可以对研究领域进行更细致的探讨。
Dec, 2022
本研究提出了一种政策优化算法,用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题,该算法在符合一定条件的 MDP 下具有较低的后悔度和约束违反率,并将其推广到弱通信 MDP 领域,为该领域提供了复杂度可行的算法。
Jan, 2022
本文提出两种基于无模型的强化学习算法,用于学习无限时间持续的平均回报 MDP 问题,第一种算法在弱相互通信的 MDPs 中,将问题简化为折扣回报问题,在 T 步之后的遗憾为 O (T^(2/3)), 该算法是解决该问题的第一种无模型的算法;第二种算法利用了对抗多臂老虎机自适应算法的最新进展,将遗憾进一步改进至 O (sqrt (T)),但需要更强的符合人类定义的遍历条件。这个结果取代了 Abbasi-Yadkori 等人 2019 年只有在符合人类定义的遍历条件下的 ergodic MDP 才能达到 O (T^(3/4)) 的遗憾。
Oct, 2019
我们提出了一种名为 LOOP 的新算法框架,它结合了基于模型和基于值的方法,用于研究无限时域平均奖励马尔可夫决策过程(AMDPs)。此外,我们提出了一个新的复杂度度量并证明了框架在几乎所有 AMDPs 中的有效性。
Apr, 2024
本文探讨了如何用线性优化的方法解决在对抗环境下的马尔科夫决策过程问题,通过将特征映射设置到线性优化的赌臂中,得到了不需要访问转移模拟器的新技术,并在探索性的假设下,将线性对手马尔科夫决策问题的最优结果从 $ ilde {O}(K^{6/7})$ 提高到了 $ ilde {O}(K^{4/5})$。
Feb, 2023
本文研究了无限时间段平均回报马尔可夫决策过程(MDP)。与现有研究不同的是,我们采用了基于通用策略梯度的算法,使其摆脱了线性 MDP 结构的约束。我们提出了一种基于策略梯度的算法,并证明了其全局收敛性质。然后我们证明该算法具有 $\tilde {\mathcal {O}}({T}^{3/4})$ 的后悔度。值得注意的是,本文是第一次对于一般参数化策略梯度算法在平均回报情景下的后悔计算进行了探索性研究。
Sep, 2023
我们提出了多种经过证明有效的无模型强化学习算法,包括基于参考优势分解的在线无模型强化学习算法以及适用于模拟器环境的无模型强化学习算法,在平均报酬马尔科夫决策过程中实现更好的折扣估计和置信区间的高效构建。
Jun, 2023