Near-Optimal Adversarial Reinforcement Learning with Switching Costs
Near-Optimal Adversarial Reinforcement Learning with Switching Costs
复制标题
DOI：
10.48550/arxiv.2302.04374
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Ming Shi;Yitao Liang;N. Shroff
中科院分区：
文献类型：
--
作者：
Ming Shi;Yitao Liang;N. Shroff
转换成本，捕捉改变策略的成本，被认为是强化学习（RL）中的一个关键指标，除了损失（或奖励）的标准指标。然而，现有的研究切换成本（与系数$\beta$，这是严格的积极和独立的$T$）主要集中在静态RL，其中的损失分布被假定为固定的学习过程中，因此，实际情况下的损失分布可能是非平稳的，甚至是敌对的不考虑。虽然对抗性强化学习更好地模拟了这类实际场景，但仍然存在一个悬而未决的问题：如何为具有切换成本的对抗性强化学习开发一个可证明有效的算法？本文为解决这一问题做了初步的努力。首先，我们提供了一个遗憾下界，表明任何算法的遗憾必须大于$\tilde{\Omega}（（H S A）^{1/3} T^{2/3}）$，其中$T$，$S$，$A$和$H$分别是每个情节中的情节，状态，动作和层数。我们的下限表明，由于对抗RL中切换成本的根本挑战，在具有切换成本的静态RL（以及没有切换成本的对抗RL）中，最佳实现的遗憾（其对$T$的依赖性为$\tilde{O}（\sqrt{T}）$）不再是可实现的。此外，我们提出了两个新的开关减少算法的遗憾，匹配我们的下限时，过渡函数是已知的，匹配我们的下限内的一个小的因素$\tilde{O}（H^{1/3}）$时，过渡函数是未知的。我们的遗憾分析证明了它们的接近最优性能。
Switching costs, which capture the costs for changing policies, are regarded as a critical metric in reinforcement learning (RL), in addition to the standard metric of losses (or rewards). However, existing studies on switching costs (with a coefficient $\beta$ that is strictly positive and is independent of $T$) have mainly focused on static RL, where the loss distribution is assumed to be fixed during the learning process, and thus practical scenarios where the loss distribution could be non-stationary or even adversarial are not considered. While adversarial RL better models this type of practical scenarios, an open problem remains: how to develop a provably efficient algorithm for adversarial RL with switching costs? This paper makes the first effort towards solving this problem. First, we provide a regret lower-bound that shows that the regret of any algorithm must be larger than $\tilde{\Omega}( ( H S A )^{1/3} T^{2/3} )$, where $T$, $S$, $A$ and $H$ are the number of episodes, states, actions and layers in each episode, respectively. Our lower bound indicates that, due to the fundamental challenge of switching costs in adversarial RL, the best achieved regret (whose dependency on $T$ is $\tilde{O}(\sqrt{T})$) in static RL with switching costs (as well as adversarial RL without switching costs) is no longer achievable. Moreover, we propose two novel switching-reduced algorithms with regrets that match our lower bound when the transition function is known, and match our lower bound within a small factor of $\tilde{O}( H^{1/3} )$ when the transition function is unknown. Our regret analysis demonstrates the near-optimal performance of them.