arXiv:2411.03107cs.LGstat.ML2024-11NeurIPS被引 5

提出新算法实现对抗性线性混合MDP的近最优动态后悔,无需非平稳性先验。

Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs

  • 融合状态占用与策略方法优势,双层结构处理环境非平稳性。
  • 首次在未知转移下达到近最优动态后悔,理论误差为O~(d√(H³K) + √(HK(H+P̄_K)))。
  • 适合研究在线强化学习中非平稳环境与未知模型的科研人员参考。

我们研究具有未知转移和对抗性奖励的周期性线性混合马尔可夫决策过程,在完全信息反馈下以动态后悔作为性能度量。通过深入分析两种主流方法——基于状态占用和基于策略的方法——发现前者擅长应对非平稳环境但难以处理未知转移,后者能有效应对未知转移却难处理非平稳性。为此,我们提出一种新算法:(i) 采用两层结构的基于状态占用的全局优化以应对非平稳性;(ii) 使用基于策略的方差感知值目标回归以应对未知转移。通过新设计的转换连接两部分。该算法达到$ ilde{/mathcal{O}}(d oot{H^3 K} + oot{HK(H + ar{P}_K)})$的动态后悔,其中 $d$ 为特征维数,$H$ 为每周期长度,$K$ 为总周期数,$ar{P}_K$ 为非平稳性度量。我们通过建立匹配的下界证明其在对数因子意义下为极小极大最优。据我们所知,这是首个在未知转移且无非平稳性先验条件下实现近最优动态后悔的成果。

原文摘要 · Abstract (English)

We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback, employing dynamic regret as the performance measure. We start with in-depth analyses of the strengths and limitations of the two most popular methods: occupancy-measure-based and policy-based methods. We observe that while the occupancy-measure-based method is effective in addressing non-stationary environments, it encounters difficulties with the unknown transition. In contrast, the policy-based method can deal with the unknown transition effectively but faces challenges in handling non-stationary environments. Building on this, we propose a novel algorithm that combines the benefits of both methods. Specifically, it employs (i) an occupancy-measure-based global optimization with a two-layer structure to handle non-stationary environments; and (ii) a policy-based variance-aware value-targeted regression to tackle the unknown transition. We bridge these two parts by a novel conversion. Our algorithm enjoys an $\widetilde{\mathcal{O}}(d \sqrt{H^3 K} + \sqrt{HK(H + \bar{P}_K)})$ dynamic regret, where $d$ is the feature dimension, $H$ is the episode length, $K$ is the number of episodes, $\bar{P}_K$ is the non-stationarity measure. We show it is minimax optimal up to logarithmic factors by establishing a matching lower bound. To the best of our knowledge, this is the first work that achieves near-optimal dynamic regret for adversarial linear mixture MDPs with the unknown transition without prior knowledge of the non-stationarity measure.

强化学习动态后悔非平稳环境线性混合MDP

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。