論文の概要: The Statistical Complexity of Interactive Decision Making

• arxiv url: http://arxiv.org/abs/2112.13487v1
• Date: Mon, 27 Dec 2021 02:53:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-28 16:11:28.113334
• Title: The Statistical Complexity of Interactive Decision Making
• Title（参考訳）: 対話的意思決定の統計的複雑性
• Authors: Dylan J. Foster and Sham M. Kakade and Jian Qian and Alexander Rakhlin
• Abstract要約: 複雑度尺度であるDecision-Estimation Coefficientは,サンプル効率のインタラクティブ学習に必要かつ十分であることが証明された。 統合アルゴリズム設計原則であるE2Dは、教師付き推定のための任意のアルゴリズムを、意思決定のためのオンラインアルゴリズムに変換する。 強化学習設定に適用すると、決定推定係数は基本的に既存のすべての硬度結果と下限を回復する。
• 参考スコア（独自算出の注目度）: 134.75192655810525
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. This question is analogous to the classical problem of optimal (supervised) statistical learning, where there are well-known complexity measures (e.g., VC dimension and Rademacher complexity) that govern the statistical complexity of learning. However, characterizing the statistical complexity of interactive learning is substantially more challenging due to the adaptive nature of the problem. The main result of this work provides a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. In particular, we provide: 1. a lower bound on the optimal regret for any interactive decision making problem, establishing the Decision-Estimation Coefficient as a fundamental limit. 2. a unified algorithm design principle, Estimation-to-Decisions (E2D), which transforms any algorithm for supervised estimation into an online algorithm for decision making. E2D attains a regret bound matching our lower bound, thereby achieving optimal sample-efficient learning as characterized by the Decision-Estimation Coefficient. Taken together, these results constitute a theory of learnability for interactive decision making. When applied to reinforcement learning settings, the Decision-Estimation Coefficient recovers essentially all existing hardness results and lower bounds. More broadly, the approach can be viewed as a decision-theoretic analogue of the classical Le Cam theory of statistical estimation; it also unifies a number of existing approaches -- both Bayesian and frequentist.
• Abstract（参考訳）: バンディット問題から強化学習まで,インタラクティブな学習と意思決定における基本的な課題は,サンプル効率が高く適応的な学習アルゴリズムを提供することである。 この問題は、学習の統計的複雑さを管理するよく知られた複雑性尺度(VC次元やラデマチャー複雑性など)が存在する、最適(教師付き)統計学習という古典的な問題に類似している。 しかし,対話型学習の統計的複雑性を特徴付けることは,問題に適応性があることから,かなり困難である。 この研究の主な結果は、サンプル効率の良い対話型学習に必要かつ十分であることが証明された、複雑性尺度、決定・推定係数を提供する。 特に、1) 対話的な意思決定問題に対する最適後悔の限界を低くし、決定推定係数を基本的な限界として確立する。 2. 統合されたアルゴリズム設計原則である推定決定(E2D)は、教師付き推定のための任意のアルゴリズムを意思決定のためのオンラインアルゴリズムに変換する。 E2Dは、我々の下界と一致する残差境界に達し、決定推定係数によって特徴づけられる最適なサンプル効率学習を実現する。 これらの結果は,対話型意思決定における学習可能性の理論を構成する。 強化学習設定に適用すると、決定推定係数は本質的に既存のハードネス結果と下限値を回復する。 より広くは、このアプローチは古典的なル・カム理論の統計的推定における決定論的類似と見なすことができる。

関連論文リスト

• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• Model-Free Reinforcement Learning with the Decision-Estimation Coefficient [79.30248422988409]
  本稿では,汎用関数近似による構造化帯域と強化学習を包含する対話型意思決定の課題について考察する。 提案手法は,値関数近似を用いたモデル自由強化学習における残差を導出し,より一般的には有効かつ不可能な構造的結果を与える。
  論文  参考訳（メタデータ） (2022-11-25T17:29:40Z)
• Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization [12.610576072466895]
  我々は、意思決定プロセスを明らかにするために、事前の意思決定データを使用する逆問題を考える。 この統計的学習問題は、データ駆動逆最適化と呼ばれる。 そこで本稿では,大規模問題を解くために,効率的なブロック座標降下に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-27T12:52:56Z)
• Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond [28.118197762236953]
  我々は,大規模な学習目標のための統一的なアルゴリズムフレームワークを開発する。 我々のフレームワークは、非回帰RL、PAC RL、報酬なし学習、モデル推定、嗜好に基づく学習など、多くの学習目標を処理する。 応用として、一般化されたDECを有界化するための自然な十分条件として「分解可能表現」を提案する。
  論文  参考訳（メタデータ） (2022-09-23T17:47:24Z)
• On data-driven chance constraint learning for mixed-integer optimization problems [0.0]
  本稿では,混合整数線形最適化問題に着目したCCL手法を提案する。 CCLは線形化可能な機械学習モデルを使用して、学習変数の条件量子を推定する。 実践者が使用するオープンアクセスソフトウェアが開発されている。
  論文  参考訳（メタデータ） (2022-07-08T11:54:39Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。 我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
  論文  参考訳（メタデータ） (2022-06-27T06:20:37Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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