2025-11-15T23:58:12.055440

An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs

Liu, Wei, Zimmert

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.

academic

改善されたモデルフリー決定推定係数と敵対的MDPへの応用

基本情報

論文ID: 2510.08882
タイトル: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
著者: Haolin Liu (バージニア大学), Chen-Yu Wei (バージニア大学), Julian Zimmert (Google Research)
分類: cs.LG (機械学習)
発表時期: 2025年10月
論文リンク: https://arxiv.org/abs/2510.08882v1

要約

本論文は構造化観測決定制定問題(DMSO)を研究している。先行研究は決定推定係数(DEC)を通じてDMSOの複雑性を特徴付けたが、後悔の上界と下界の間にモデルクラスサイズに関連するギャップを残していた。Foster等(2023b)は楽観的DECを導入してこのギャップを縮小し、値関数クラスサイズのみに関連する界を実現した。しかし、楽観性に基づく探索は確率的環境のみを処理でき、敵対的環境への拡張が可能かどうかは不明確である。

本論文はDig-DECを提案する。これはモデルフリーのDEC手法であり、楽観性を除去し、純粋に情報利得によって探索を駆動する。Dig-DECは常に楽観的DEC以下であり、特殊な場合には著しく小さくなる可能性がある。重要なことに、楽観性の除去により、明示的な報酬推定器なしに敵対的環境を処理できる。Dig-DECを確率的遷移と敵対的報酬を持つハイブリッドMDPに適用することで、複数の一般的な遷移構造下でバンディットフィードバックを持つハイブリッドMDPの最初のモデルフリー後悔界を得た。

研究背景と動機

解決すべき問題: 既存の決定推定係数(DEC)フレームワークはモデルクラスサイズと値関数クラスサイズの間にギャップが存在し、楽観性に基づく手法は敵対的環境を効果的に処理できない。
問題の重要性:
- オンライン決定制定は強化学習の中核問題である
- 実際の応用では部分的に確率的、部分的に敵対的なハイブリッド環境に直面することが多い
- 既存手法の理論的保証と実際の性能の間にギャップが存在する
既存手法の限界:
- Foster等のモデルはDEC/E2Dに基づき、log|M|のモデル推定コストを負担する必要がある
- 楽観的DECは複雑性を改善したが、楽観原理に依存し、敵対的設定を処理できない
- Liu等(2025)のハイブリッドMDP手法は全情報フィードバックのみを処理でき、バンディット状況は未解決問題である
研究動機: 確率的環境で既存結果を改善でき、同時にハイブリッドMDPのバンディットフィードバック状況を初めて処理できる統一フレームワークを開発する。

核心的貢献

Dig-DEC複雑性度量の提案: 双情報利得決定推定係数を導入し、楽観性を除去し、純粋に情報利得によって探索を駆動する
統一理論フレームワーク: 確率的環境とハイブリッド環境を同時に処理できる汎用アルゴリズムフレームワークを構築
改善されたオンライン関数推定:
- 平均推定誤差: T^{3/4}/T^{5/6}からT^{2/3}/T^{7/9}に改善
- 二乗誤差: T^{2/3}から√Tに改善。Bellman完備MDPで初めて楽観的手法と同じ性能を達成
未解決問題の解決: ハイブリッドMDPがバンディットフィードバック下での最初のモデルフリー後悔界を提供

手法の詳細

タスク定義

DMSOフレームワーク: モデル空間M、戦略空間Π、観測空間O、値関数Vが与えられたとき、各ラウンドtにおいて:

環境はモデルMt ∈ Mを選択
学習者は戦略πt ∈ Πを選択
観測ot ~ Mt(·|πt)を得る
目標: 後悔Reg(π*) = Σt(VMt(π*) - VMt(πt))を最小化

Φ-制限環境: 情報集合Φによってm×Πを分割し、各情報集合ϕは単一の戦略πϕを含む。

モデルアーキテクチャ

1. 汎用フレームワーク(アルゴリズム1)

核心的な考え方は以下の鞍点問題を解くことである:

min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} AIR^{Φ,D}_η(p,ν;ρt)

ここで発散度量は:

D^π(ν||ρ) = E_{M~ν}E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ) + E_{ϕ~ρ}[D^π(ϕ||M)]]

2. Dig-DEC定義

dig-dec^{Φ,D}_η = max_{ρ∈Δ(Φ)} min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} 
E_{π~p}E_{(M,π*)~ν}[V_M(π*) - V_M(π) - (1/η)E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ)] - (1/η)E_{ϕ~ρ}[D^π(ϕ||M)]]

3. 事後更新メカニズム

Dの異なる選択に応じて:

平均推定誤差: バッチ処理アルゴリズム(アルゴリズム2)を使用
二乗推定誤差: 双層学習アルゴリズム(アルゴリズム3)を使用

技術的革新点

双情報利得設計:
- KL項は正則化に使用され、楽観的メカニズムを回避
- D^π項は分布差異を捉え、厳密な改善を実現
楽観性の除去: 楽観的DECのV_ϕ(π_ϕ)項をKL(ν_{ϕ}, ρ)正則化項で置き換え
改善された推定手順:
- 平均誤差: 偏った推定器を不偏推定器で置き換え
- 二乗誤差: 双時間スケール手順を再設計し、Est界をT^{1/3}から定数に改善