arXiv:2608.06545cs.LGmath.OC2026-08

提出鲁棒平均回报MDP的最优学习方法,解决模型不确定下的样本效率问题。

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

  • 通过插件还原法设计自适应算法,动态选择名义或鲁棒性策略
  • 揭示了σH₀为容忍度分界点,样本复杂度在高低容忍区呈现不同形式
  • 适用于需应对模型不确定性且对鲁棒性要求高的强化学习场景

分布鲁棒马尔可夫决策过程为模型不确定下的序列决策提供了合理框架。本文研究在平均回报准则下,学习ε-最优鲁棒策略所需的最少样本数。生成模型提供来自名义转移核的样本,而策略性能在以(s,a)为单位的总变差不确定性集(半径不超过σ)上评估。设H₀和H_σ分别表示名义与鲁棒最优偏移跨度。我们识别出σH₀为高/低容忍度区间的分界扰动尺度。匹配的上下界表明,忽略对数因子,最小最大总样本复杂度为 NSA ≍ (SA/ε²) × { min{H₀,H_σ}, 当 ε ≳ σH₀;min{H₀,H_σ} + σH_σ², 当 ε ≲ σH₀ }。其中S、A分别为状态数和动作数,N为每状态-动作对的样本数。样本复杂度包含类名义AMDPC的线性跨度项,以及仅在低容忍度情形出现的鲁棒性特异性项。我们通过基于还原的插件程序实现这些速率,该程序选择还原方式(名义或鲁棒)及折扣因子:一种使用已知跨度参数的跨度知情程序,以及一种从数据中校准两者的跨度无关程序。

原文摘要 · Abstract (English)

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an $\varepsilon$-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over $(s,a)$-rectangular total-variation uncertainty sets of radius at most $σ$. Let $H_0$ and $H_σ$ denote the nominal and robust optimal bias spans, respectively. We identify $σH_0$ as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is $$ NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases} $$ Here $S$ and $A$ are the numbers of states and actions, and $N$ is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

强化学习鲁棒决策样本效率

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