論文の概要: Minimax PAC Bounds for Learning in Exogenous Contextual MDPs

• arxiv url: http://arxiv.org/abs/2606.25170v1
• Date: Tue, 23 Jun 2026 21:02:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-25 17:05:30.143759
• Title: Minimax PAC Bounds for Learning in Exogenous Contextual MDPs
• Title（参考訳）: 外部文脈型MDPにおける学習のためのミニマックスPAC境界
• Authors: Corentin Pla, Hugo Richard, Marc Abeille, Vianney Perchet,
• Abstract要約: PAC学習は、割引係数$$、有限状態空間$mathcal X$、アクション空間$mathcal A$、コンテキスト空間$mathcal Z$を含む割引決定プロセスにおける。
• 参考スコア（独自算出の注目度）: 26.599514971653615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts, with discount factor $γ$, finite state space $\mathcal X$, action space $\mathcal A$, and context space $\mathcal Z$. At each time step, a context is drawn independently from an unknown distribution $μ$ and revealed before the agent acts. This context may affect both rewards and transitions, while remaining uncontrolled by the agent. Depending on the regime, the learner has access either to a sampling oracle for $μ$, to a sampling oracle for the transition kernel conditioned on state-context-action tuples, or to both. Oracles can be accessed before and during policy execution. The sample complexity is measured by a couple $(n,m)$, where $n$ is the number of calls to the sampling oracles before execution and $m$ is the number of calls to the sampling oracles during execution. When rewards and transitions are known and only the context distribution $μ$ is sampled, we give a variance-reduced algorithm that solves policy evaluation (PE), best-value estimation (BVE), and best-policy extraction (BPE) with $\left(\widetilde O\left(1/((1-γ)^3\varepsilon^2)\right), 0 \right) $ sample complexity. The rate is independent of $|\mathcal Z|$ and minimax optimal up to logarithmic factors. As a corollary, we also obtain tight rates in the case of one-step perfect look-ahead, improving upon the existing guarantees. In the fully unknown regime, where both $μ$ and P must be learned, we show that PE remains $|\mathcal Z|$-free, with matching upper and lower bounds $\bigl(\widetilde O(|\mathcal X|/((1-γ)^3\varepsilon^2)),\, \widetilde O(1/((1-γ)^2\varepsilon^2))\bigr)$.
• Abstract（参考訳）: 我々は、表付き割引マルコフ決定過程におけるPAC学習を、外因性(exogenous)な文脈で、割引係数$γ$、有限状態空間$\mathcal X$、アクション空間$\mathcal A$、コンテキスト空間$\mathcal Z$で研究する。 各ステップにおいて、コンテキストは未知の分布から$μ$から独立して引き出され、エージェントが作用する前に明らかにされる。 この文脈は報酬と移行の両方に影響しうるが、エージェントによって制御されないままである。 規則によっては、学習者は、$μ$のサンプリングオラクル、状態-コンテキスト-アクションタプルで条件付けられた遷移カーネルのサンプリングオラクル、または両方にアクセスすることができる。 Oracleはポリシー実行前後にアクセスできる。 サンプルの複雑さは2組の$(n,m)$で測定され、$n$は実行前のサンプリングオークルへの呼び出し数、$m$は実行時のサンプリングオークルへの呼び出し数である。 報酬と遷移が知られ、文脈分布が$μ$のみがサンプリングされるとき、政策評価(PE)、ベスト値推定(BVE)、そして、$\left(\widetilde O\left(1/((1-γ)^3\varepsilon^2)\right), 0 \right)のサンプル複雑性を持つBPE(BPE)を解く分散還元アルゴリズムを与える。 このレートは$|\mathcal Z|$とminimaxの対数係数に最適である。 また,1段階の完全ルックアヘッドの場合においても厳格なレートが得られ,既存の保証も改善される。 μ$とPの両方を学習しなければならない完全に未知の状態において、PE は $|\mathcal Z|$-free のままであり、一致する上界と下界は $\bigl(\widetilde O(|\mathcal X|//((1-γ)^3\varepsilon^2),\, \widetilde O(1/((1-γ)^2\varepsilon^2))\bigr)$である。

関連論文リスト

• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• 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)
• Faster Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk [28.431572772564518]
  我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。 我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
  論文  参考訳（メタデータ） (2022-06-19T11:33:07Z)
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
  タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。 このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。 情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
  論文  参考訳（メタデータ） (2021-08-11T20:42:46Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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