提出新方法解决对抗性强化学习中的决策复杂度问题,提升模型泛化能力。
An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
- 用信息增益驱动探索,无需乐观估计,适用于对抗环境。
- 在混合MDP中首次实现无模型后悔界,改进了多项式时间性能。
- 适合研究对抗性强化学习与在线函数估计的学者参考。
我们研究结构化观测下的决策问题(DMSO)。先前工作通过决策-估计系数(DEC)刻画了其复杂度,但遗憾的是,上界与下界之间存在与模型类大小相关的差距。为缩小这一差距,Foster等人(2023b)引入了乐观型DEC,其边界仅依赖于值函数类大小。然而,该方法仅适用于随机环境,其能否扩展至对抗性设置尚不明确。本文提出Dig-DEC——一种无模型、无需乐观性的DEC,仅依靠信息增益驱动探索。Dig-DEC始终不大于乐观型DEC,且在特定情况下可显著更小。更重要的是,去除了乐观性使其无需显式奖励估计即可处理对抗环境。将Dig-DEC应用于具有随机转移和对抗性奖励的混合MDP,在多种一般转移结构下,首次获得带棋盘反馈的无模型后悔界,解决了Liu等(2025)提出的主开放问题。此外,我们改进了无模型学习中的在线函数估计过程:对于平均误差最小化,重构估计器,使集中性更优,后悔界从$T^{3/4}$(策略内)降至$T^{2/3}$,从$T^{5/6}$(策略外)降至$T^{7/9}$;对于贝尔曼完备MDP中的平方误差最小化,重设计两时间尺度算法,将后悔界从$T^{2/3}$提升至$\ ext{\sqrt{T}}$。这是首个在贝尔曼完备MDP中性能匹配乐观方法(Jin et al., 2021; Xie et al., 2023)的基于DEC的方法。
原文摘要 · Abstract (English)
We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coefficient (DEC), but left a gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, Foster et al. (2023b) introduced optimistic DEC, achieving a bound that scales only with the size of the value-function class. However, their optimism-based exploration is only known to handle the stochastic setting, and it remains unclear whether it extends to the adversarial setting. We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Importantly, the removal of optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under several general transition structures, resolving the main open problem left by Liu et al. (2025). We also improve the online function-estimation procedure in model-free learning: For average estimation error minimization, we refine the estimator in Foster et al. (2023b) to achieve sharper concentration, improving their regret bounds from $T^{3/4}$ to $T^{2/3}$ (on-policy) and from $T^{5/6}$ to $T^{7/9}$ (off-policy). For squared error minimization in Bellman-complete MDPs, we redesign their two-timescale procedure, improving the regret bound from $T^{2/3}$ to $\sqrt{T}$. This is the first time a DEC-based method achieves performance matching that of optimism-based approaches (Jin et al., 2021; Xie et al., 2023) in Bellman-complete MDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。