論文の概要: Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

• arxiv url: http://arxiv.org/abs/2010.03104v1
• Date: Wed, 7 Oct 2020 01:33:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-09 22:45:18.714475
• Title: Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Title（参考訳）: 文脈帯域のインスタンス依存的複雑度と強化学習:診断に基づく視点
• Authors: Dylan J. Foster and Alexander Rakhlin and David Simchi-Levi and Yunzong Xu
• Abstract要約: 古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
• 参考スコア（独自算出の注目度）: 104.67295710363679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the classical multi-armed bandit problem, instance-dependent algorithms attain improved performance on "easy" problems with a gap between the best and second-best arm. Are similar guarantees possible for contextual bandits? While positive results are known for certain special cases, there is no general theory characterizing when and how instance-dependent regret bounds for contextual bandits can be achieved for rich, general classes of policies. We introduce a family of complexity measures that are both sufficient and necessary to obtain instance-dependent regret bounds. We then introduce new oracle-efficient algorithms which adapt to the gap whenever possible, while also attaining the minimax rate in the worst case. Finally, we provide structural results that tie together a number of complexity measures previously proposed throughout contextual bandits, reinforcement learning, and active learning and elucidate their role in determining the optimal instance-dependent regret. In a large-scale empirical evaluation, we find that our approach often gives superior results for challenging exploration problems. Turning our focus to reinforcement learning with function approximation, we develop new oracle-efficient algorithms for reinforcement learning with rich observations that obtain optimal gap-dependent sample complexity.
• Abstract（参考訳）: 古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 同様の保証は文脈的盗賊には可能か? ポジティブな結果が特定の特別なケースで知られているが、リッチで一般的なポリシーのクラスに対して、コンテキストのバンディットに対するインスタンス依存の後悔の境界がいつどのように達成できるかを特徴付ける一般的な理論は存在しない。 インスタンス依存の後悔境界を得るのに十分かつ必要な複雑性尺度のファミリーを導入する。 次に,可能な限りギャップに適応する新たなoracle効率の高いアルゴリズムを導入すると同時に,最悪の場合のminimax率も実現します。 最後に,従来提案されてきたコンテキスト的帯域幅,強化学習,アクティブラーニングなど,多くの複雑性対策を組み合わせ,最適なインスタンス依存後悔を決定する上での役割を解明する構造的結果を提供する。 大規模な経験的評価では,本手法が探索問題に対して優れた結果をもたらすことがしばしばある。 関数近似による強化学習に重点を移し,ギャップ依存的なサンプル複雑性を得るために,oracle による強化学習のための新しいアルゴリズムを開発した。

関連論文リスト

• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  頑健な学習における根本的な問題は非対称性である: 学習者は指数関数的に多くの摂動の全てを正しく分類する必要がある。 これとは対照的に、攻撃者は1つの摂動を成功させる必要がある。 本稿では,新しいマルチグループ設定を導入し,新しいマルチロバスト学習問題を提案する。
  論文  参考訳（メタデータ） (2023-03-15T21:30:14Z)
• Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design [12.056495277232118]
  この研究は、ほぼ最適ポリシーを学ぶことの「インスタンスに依存した」複雑さを理解することを目的としている。 本稿では,複雑性の詳細なインスタンス依存尺度を実現するアルゴリズムである textscPedel を提案する。 我々は、textscPedel が低regret, minimax-optimal アルゴリズムよりも有益であることを示す。
  論文  参考訳（メタデータ） (2022-07-06T10:42:57Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。 特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。 以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
  論文  参考訳（メタデータ） (2022-02-08T16:39:57Z)
• Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
  構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。 平均的な武器の報酬は、与えられた構造的制約を満たす。 我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-07-02T08:59:54Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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