論文の概要: Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

• arxiv url: http://arxiv.org/abs/2605.19768v1
• Date: Tue, 19 May 2026 12:39:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-20 15:03:09.332017
• Title: Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
• Title（参考訳）: 多項ロジスティックMDPのための最小変数対応レギュレット境界
• Authors: Pierre Boudart, Pierre Gaillard, Alessandro Rudi,
• Abstract要約: 既存のマルコフ決定過程のアルゴリズムは、$smashtildeO(dH2sqrtT)$を後悔する。 本稿では,最悪の場合において既存の境界を復元し,構造化されたMDPに対して改善する,$smashtildeO(dH2bar_TsqrtT)$の後悔を実現するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 56.28491566735463
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study reinforcement learning for episodic Markov Decision Processes (MDPs) whose transitions are modelled by a multinomial logistic (MNL) model. Existing algorithms for MNL mixture MDPs yield a regret of $\smash{\tilde{O}(dH^2\sqrt{T})}$ (Li et al., 2024), where $d$ is the feature dimension, $H$ the episode length, and $T$ the number of episodes. Inspired by the logistic bandit literature (Abeille et al., 2021; Faury et al., 2022; Boudart et al., 2026), we introduce a problem-dependent constant $\barσ\_T \leq 1/2$, measuring the normalised average variance of the optimal downstream value function along the learner's trajectory. We propose an algorithm achieving a regret of $\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}$, which recovers the existing bound in the worst case and improves upon it for structured MDPs. For instance, for KL-constrained robust MDPs, $\barσ\_T = O(H^{-1})$, reducing the horizon dependence by a factor $H$. We further establish a matching $\smash{Ω(dH^2\barσ\_T\sqrt{T})}$ lower bound, proving minimax optimality (up to logarithmic factors) and fully characterising the regret complexity of MNL mixture MDPs for the first time.
• Abstract（参考訳）: 我々は,多項ロジスティック(MNL)モデルを用いて遷移をモデル化した表在的マルコフ決定過程(MDP)の強化学習について検討した。 MNL混合MDPの既存のアルゴリズムは、$\smash{\tilde{O}(dH^2\sqrt{T})}$ (Li et al , 2024)を後悔する。 Abeille et al , 2021; Faury et al , 2022; Boudart et al , 2026) に着想を得て, 学習者の軌道に沿った最適下流値関数の正規化平均分散を測定する問題依存定数 $\barσ\_T \leq 1/2$ を導入する。 本稿では, 最悪の場合において既存の境界を回復し, 構造化された MDP に対して改善する, $\smash{\tilde{O}(dH^2\barσ\_T\sqrt{T})}$ の遺残を解くアルゴリズムを提案する。 例えば、KL に制約されたロバスト MDP に対して、$\barσ\_T = O(H^{-1})$ であり、地平面依存性を$H$ で減少させる。 さらに、マッチング $\smash{Ω(dH^2\barσ\_T\sqrt{T})} を下界に設定し、最小値最適性(対数因子まで)を証明し、MNL混合MDPの後悔の複雑さを初めて完全に特徴づける。

関連論文リスト

• Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation [3.2703356989962518]
  非線型関数近似を用いたモデルに基づく強化学習について検討する。 本研究では,無限水平平均逆法と割引逆法の両方に有効である確率効率のよい値反復型アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-06-19T15:29:14Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。 上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。 我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
  論文  参考訳（メタデータ） (2020-12-15T18:56:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。