arXiv:2511.18247cs.LGmath.OC2025-11

分析乐观强化学习的后悔分布尾部,给出更精细的性能保证。

Tail Distribution of Regret in Optimistic Reinforcement Learning

  • 基于乐观探索设计算法,刻画后悔的尾部概率分布。
  • 发现后悔分布具双阶段结构:先亚高斯后亚威布尔尾部。
  • 适用于关注风险控制与鲁棒性评估的研究者。

本文针对未知转移动态的有限时域表格型马尔可夫决策过程,推导了基于乐观策略的强化学习算法的实例相关后悔尾部界。首先研究一种类似UCBVI(基于模型)的算法,通过显式边界刻画累积后悔 $R_K$ 超过阈值 $x$ 的概率 $P(R_K \> x)$,超越仅分析期望 $E[R_K]$ 或单个高概率分位数的传统方法。考虑两种自然的探索奖励调度:(i) 依赖总轮次 $K$ 的方案;(ii) 不依赖 $K$(即任意时间)的方案,仅基于当前轮次索引。随后补充对乐观Q-learning(无模型)在 $K$-依赖奖励下的分析。在基于模型与无模型设置下,均获得 $P(R_K \> x)$ 的上界,具有独特的两阶段结构:从实例相关尺度起始的亚高斯尾部,持续至过渡阈值,之后转为亚威布尔尾部。进一步推导出 $E[R_K]$ 的实例相关上界。所提算法依赖调参 $α$,用于平衡期望后悔与亚高斯衰减范围。

原文摘要 · Abstract (English)

We derive instance-dependent tail bounds for the regret of optimism-based reinforcement learning in finite-horizon tabular Markov decision processes with unknown transition dynamics. We first study a UCBVI-type (model-based) algorithm and characterize the tail distribution of the cumulative regret $R_K$ over $K$ episodes via explicit bounds on $P(R_K \ge x)$, going beyond analyses limited to $E[R_K]$ or a single high-probability quantile. We analyze two natural exploration-bonus schedules for UCBVI: (i) a $K$-dependent scheme that explicitly incorporates the total number of episodes $K$, and (ii) a $K$-independent (anytime) scheme that depends only on the current episode index. We then complement the model-based results with an analysis of optimistic Q-learning (model-free) under a $K$-dependent bonus schedule. Across both the model-based and model-free settings, we obtain upper bounds on $P(R_K \ge x)$ with a distinctive two-regime structure: a sub-Gaussian tail starting from an instance-dependent scale up to a transition threshold, followed by a sub-Weibull tail beyond that point. We further derive corresponding instance-dependent bounds on the expected regret $E[R_K]$. The proposed algorithms depend on a tuning parameter $α$, which balances the expected regret and the range over which the regret exhibits sub-Gaussian decay.

强化学习后悔分析概率界

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