論文の概要: On the Complexity of Adversarial Decision Making

• arxiv url: http://arxiv.org/abs/2206.13063v1
• Date: Mon, 27 Jun 2022 06:20:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-28 15:27:34.594237
• Title: On the Complexity of Adversarial Decision Making
• Title（参考訳）: 逆方向決定の複雑さについて
• Authors: Dylan J. Foster and Alexander Rakhlin and Ayush Sekhari and Karthik Sridharan
• Abstract要約: 決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。 我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
• 参考スコア（独自算出の注目度）: 101.14158787665252
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A central problem in online learning and decision making -- from bandits to reinforcement learning -- is to understand what modeling assumptions lead to sample-efficient learning guarantees. We consider a general adversarial decision making framework that encompasses (structured) bandit problems with adversarial rewards and reinforcement learning problems with adversarial dynamics. Our main result is to show -- via new upper and lower bounds -- that the Decision-Estimation Coefficient, a complexity measure introduced by Foster et al. in the stochastic counterpart to our setting, is necessary and sufficient to obtain low regret for adversarial decision making. However, compared to the stochastic setting, one must apply the Decision-Estimation Coefficient to the convex hull of the class of models (or, hypotheses) under consideration. This establishes that the price of accommodating adversarial rewards or dynamics is governed by the behavior of the model class under convexification, and recovers a number of existing results -- both positive and negative. En route to obtaining these guarantees, we provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures, including the Information Ratio of Russo and Van Roy and the Exploration-by-Optimization objective of Lattimore and Gy\"{o}rgy.
• Abstract（参考訳）: オンライン学習と意思決定における中心的な問題は、盗賊から強化学習まで、モデリング仮定がサンプル効率の学習保証につながるものを理解することである。 本稿では,対人報酬を伴う(構造化された)帯域幅問題と,対人力学による強化学習問題を含む一般対人意思決定フレームワークについて考察する。 我々の主な結果は、新しい上界と下界を通じて、フォスターらが確率的に導入した複雑性尺度である意思決定係数が、敵対的意思決定に対して低い後悔を得るのに必要かつ十分であることを示すことである。 しかし、確率的な設定と比較して、決定推定係数をモデル(または仮説)のクラスの凸殻に適用しなければならない。 これにより、敵対的報酬やダイナミクスを満たすコストは、凸化下のモデルクラスの振る舞いによって制御され、多くの既存の結果(正と負の両方)を回復する。 これらの保証を得るためには,russo と van roy の情報比や lattimore と gy\"{o}rgy の探索・最適化目標など,他のよく知られた複雑性尺度の変種と決定推定係数を結びつける新たな構造的結果を提供する。

関連論文リスト

• Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability [71.82666334363174]
  我々は,統計的推定と対話的意思決定において,下位境界法のための統一的なフレームワークを開発する。 対話型意思決定のための新しい下位境界の複雑さを促進する新しい尺度である決定次元を導入する。
  論文  参考訳（メタデータ） (2024-10-07T15:14:58Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• A Meta-heuristic Approach to Estimate and Explain Classifier Uncertainty [0.4264192013842096]
  本研究は,人間と機械学習の双方の意思決定に相互に関係する因子の観点から,インスタンスの複雑性を特徴付けるクラス非依存型メタヒューリスティックスを提案する。 提案された測度とフレームワークは、より複雑なインスタンスのモデル開発を改善するとともに、モデルの棄却と説明の新しい手段を提供するという約束を持っている。
  論文  参考訳（メタデータ） (2023-04-20T13:09:28Z)
• 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)
• The Statistical Complexity of Interactive Decision Making [126.04974881555094]
  複雑度尺度であるDecision-Estimation Coefficientは,サンプル効率のインタラクティブ学習に必要かつ十分であることが証明された。 統合アルゴリズム設計原則であるE2Dは、教師付き推定のための任意のアルゴリズムを、意思決定のためのオンラインアルゴリズムに変換する。
  論文  参考訳（メタデータ） (2021-12-27T02:53:44Z)
• Risk-Sensitive Reinforcement Learning: a Martingale Approach to Reward Uncertainty [15.572157454411533]
  逐次意思決定問題における不確実性に対する感性を考慮した新しい枠組みを提案する。 本稿では,プロセスのDoob分解に基づく累積報酬に含まれるランダム性の新たな分解について述べる。 我々は、この新たなリスクに敏感なアプローチを、ポリシーと値勾配関数に基づくモデルフリーアルゴリズムに取り入れることで、強化学習の側面を革新し、グリッドの世界とポートフォリオ最適化の問題にその関連性を示す。
  論文  参考訳（メタデータ） (2020-06-23T01:20:00Z)

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

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