Provably Efficient Model-Free Algorithms for Non-stationary CMDPs
Provably Efficient Model-Free Algorithms for Non-stationary CMDPs
复制标题
DOI：
10.48550/arxiv.2303.05733
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Honghao Wei;A. Ghosh;N. Shroff;Lei Ying;Xingyu Zhou
中科院分区：
文献类型：
--
作者：
Honghao Wei;A. Ghosh;N. Shroff;Lei Ying;Xingyu Zhou
我们研究了无模型强化学习（RL）算法在情节非平稳约束马尔可夫决策过程（CMDPs），其中代理的目标是最大化预期的累积奖励的预期效用（成本）的累积约束。在非平稳环境中，只要累积变化不超过某些变化预算，奖励、效用函数和过渡内核可以随时间任意变化。我们提出了第一个无模型、无模拟器的RL算法，该算法在表格和线性函数逼近设置中针对非平稳CIDP具有次线性遗憾和零约束违反，并具有可证明的性能保证。我们的结果上的遗憾界和约束违反表格的情况下相匹配的最佳结果为固定CMDPs时，总预算是已知的。此外，我们提出了一个通用的框架，用于解决与分析非平稳CMDPs相关的众所周知的挑战，而不需要事先知道的变化预算。我们适用于表格和线性近似设置的方法。
We study model-free reinforcement learning (RL) algorithms in episodic non-stationary constrained Markov Decision Processes (CMDPs), in which an agent aims to maximize the expected cumulative reward subject to a cumulative constraint on the expected utility (cost). In the non-stationary environment, reward, utility functions, and transition kernels can vary arbitrarily over time as long as the cumulative variations do not exceed certain variation budgets. We propose the first model-free, simulator-free RL algorithms with sublinear regret and zero constraint violation for non-stationary CMDPs in both tabular and linear function approximation settings with provable performance guarantees. Our results on regret bound and constraint violation for the tabular case match the corresponding best results for stationary CMDPs when the total budget is known. Additionally, we present a general framework for addressing the well-known challenges associated with analyzing non-stationary CMDPs, without requiring prior knowledge of the variation budget. We apply the approach for both tabular and linear approximation settings.