論文の概要: Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models
- arxiv url: http://arxiv.org/abs/2611.05562v1
- Date: Tue, 03 Nov 2026 19:54:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 03:25:57.832876
- Title: Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models
- Title（参考訳）: 生成モデルに基づく多目的強化学習のためのニアミニマックスサンプル複雑度
- Abstract要約: 有限割引マルコフ決定過程を未知の遷移、$S$状態、$A$アクション、および$m$既知の報酬関数を用いて研究する。
学習者はこれらの報酬のすべての凸組み合わせに対して$varepsilon$-optimal Policyを提供する必要がある。
- 参考スコア（独自算出の注目度）: 3.053409604085541
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In multi-objective reinforcement learning, preferences may be specified only after data collection, requiring one dataset to support a continuum of reward trade-offs. We study finite discounted Markov decision processes with unknown transitions, $S$ states, $A$ actions, and $m$ known reward functions taking values in $[0,1]$, given access to a generative model. The learner must provide an $\varepsilon$-optimal policy for every convex combination of these rewards without further sampling, with a guarantee that holds simultaneously over all preferences and initial states. Writing $H=(1-γ)^{-1}$, we establish the constant-confidence minimax sample complexity $\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right)$, where the suppressed factors are logarithmic in $S,A,H,\varepsilon^{-1}$ and the dependence on $m$ is explicit. Thus, up to these logarithmic factors, the worst-case statistical cost of supporting all preferences grows logarithmically with the number of objectives and saturates at the number of states. The upper bound uses uniform state--action sampling and empirical planning, with reward rounding in the logarithmic-objective regime. Its analysis chains optimal-value increments over covers of the reward hull. A one-sided Bellman variance bound controls signed value differences under a second transition kernel, preserving the $H^3\varepsilon^{-2}$ dependence. A complementary uniform guarantee for all bounded rewards yields the state-dimension saturation. We establish lower bounds matching up to logarithmic factors through a rare-exit construction with subset rewards and action encoding. These bounds apply to adaptive simulator queries and arbitrary randomized history-dependent output policies, while the upper bounds are attained by deterministic stationary policies.
- Abstract（参考訳）: 多目的強化学習では、好みはデータ収集後にのみ指定でき、1つのデータセットが報酬トレードオフの継続をサポートする必要がある。
我々は、生成モデルへのアクセスを前提として、有限割引マルコフ決定過程、未知の遷移、$S$状態、$A$アクション、および$m$既知の報酬関数について研究する。
学習者は、これらの報酬のすべての凸組み合わせに対して、さらにサンプリングすることなく、$\varepsilon$-optimal Policyを提供しなければならない。
H=(1-γ)^{-1}$と書くと、定数自信のミニマックスサンプル複雑性を$\widetilde\!
\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right)$ ここで、抑制された因子は$S,A,H,\varepsilon^{-1}$で対数であり、$m$への依存は明示的である。
このように、これらの対数的要因により、全ての選好を支持する最悪の統計的コストは、目的の個数と対数的に増加し、状態の個数で飽和する。
上界は均一な状態-行動サンプリングと経験的計画を使い、対数目的体制では報酬を丸めている。
その分析は報酬船体のカバーの上に最適値のインクリメントを連鎖させる。
H^3\varepsilon^{-2}$依存を保存する一方のベルマン分散は、第2の遷移カーネルの下で符号値の差を制御している。
すべての有界報酬に対する相補的一様保証は、状態次元飽和をもたらす。
サブセットの報酬とアクションエンコーディングによる稀な外部構成により、対数的要因に一致する下位境界を確立する。
これらの境界は適応型シミュレータクエリと任意のランダム化された履歴依存の出力ポリシーに適用され、上位境界は決定論的定常ポリシーによって達成される。
関連論文リスト
- Near Minimax Rate for Quantile Distributional Reinforcement Learning [9.454986540713655]
我々は、経験的マルコフ決定過程から量子的不動点推定器$bm_m(n)$を構築し、ワッサーシュタイン距離の下で非漸近誤差境界を確立する。
報酬密度が 0 から一様に有界であるとき、すべての解像度に対して同時に有界なroot-$n$高確率が得られる。
p>2$ の場合、係数 $m1/2-1/p$ のルート-$n$ と、すべての有限に対して遅くて解像度に依存しない $n-1/p$ を定めます。
論文 参考訳（メタデータ） (2026-10-21T11:35:36Z) - Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness [0.0]
本研究では,未知の,未知の,未知の,未知の事例の残差に基づく実存可能なブール学習について検討する。
決定論的学習、任意の有限類に対する極小$$レギュレーション、VC 1 の有限類に対するすべての濃度-再現性レギュレーションを特徴付ける。
論文 参考訳（メタデータ） (2026-10-18T05:17:14Z) - Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits [24.636690767654333]
線形報酬構造を持つコンテキスト帯において,K$ターゲットポリシーを同時に評価する方法を検討する。
PRISMAは、全ての目標ポリシーの値を、少なくとも1-$の確率で精度$varepsilon$に推定するアルゴリズムである。
論文 参考訳（メタデータ） (2026-10-15T17:22:59Z) - Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds [61.41272490044518]
REINFORCEの分散還元バージョンは、$O(-3)$サンプルの複雑さを改善して$$-stationary点を求める。
本稿では, 従来の重みの分散を仮定することなく, 同一レートを達成できる, 防御重要度サンプリングに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-10-02T11:43:52Z) - A Convergence Framework for Deep $V$-Learning: Error Propagation and Sharp Action-Gap Bounds [0.0]
更新エラーを、フィッティング、遷移再利用、ターゲット構築、リプレイ、アクション選択、探索の6つの残差に分解する。
次数$n-$の統計的誤差境界に対して、最適連続割り当てと、制約された最適値の係数2$以内の整数割り当てを導出する。
これらの結果から, FIFO/インターリーブされたSGDに対して, 厳密な動作スコアを有する固定水平生成-リセット近似-ERM法に対して, 期待されるポリシ-ロス一貫性が得られた。
論文 参考訳（メタデータ） (2026-09-16T15:03:46Z) - Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳（メタデータ） (2026-08-06T19:49:48Z) - The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。
ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。
我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
論文 参考訳（メタデータ） (2026-05-28T09:12:20Z) - How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
r*(x) = *(langle *, xrangle)$ と $x sim N(0, I_d)$ でガウスの単一インデックスモデルでフィードバックを研究する。
まず、報酬重み付きサンプルから隠れた方向を*$で学習し、次に重み付きリッジ回帰により読み出し層に適合する2段階のニューラル報酬モデルを分析する。
論文 参考訳（メタデータ） (2026-05-23T22:00:38Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Reward-Free Model-Based Reinforcement Learning with Linear Function
Approximation [92.99933928528797]
エピソードマルコフ決定過程(MDP)に対する線形関数近似を用いたモデルに基づく無報酬強化学習について検討する。
計画段階では、特定の報酬関数が与えられ、探索フェーズから収集したサンプルを使用して良い政策を学ぶ。
任意の報酬関数に対して$epsilon$-optimal Policyを得るには,最大$tilde O(H4d(H + d)epsilon-2)$ episodesをサンプリングする必要がある。
論文 参考訳（メタデータ） (2021-10-12T23:03:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。