論文の概要: Contextual Bandits with Large Action Spaces: Made Practical
- arxiv url: http://arxiv.org/abs/2207.05836v1
- Date: Tue, 12 Jul 2022 21:01:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-14 12:23:04.627053
- Title: Contextual Bandits with Large Action Spaces: Made Practical
- Title(参考訳): 大きなアクション空間を持つコンテキスト帯域:実践的
- Authors: Yinglun Zhu, Dylan J. Foster, John Langford, Paul Mineiro
- Abstract要約: 本稿では,連続的かつ線形に構造化された行動空間を持つコンテキスト的帯域に対する,最初の効率的汎用アルゴリズムを提案する。
提案アルゴリズムは,教師付き学習のための計算オラクル,および (ii) 動作空間を最適化し, 動作空間のサイズによらず, サンプルの複雑性, 実行時間, メモリを実現する。
- 参考スコア(独自算出の注目度): 48.28690486203131
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A central problem in sequential decision making is to develop algorithms that
are practical and computationally efficient, yet support the use of flexible,
general-purpose models. Focusing on the contextual bandit problem, recent
progress provides provably efficient algorithms with strong empirical
performance when the number of possible alternatives ("actions") is small, but
guarantees for decision making in large, continuous action spaces have remained
elusive, leading to a significant gap between theory and practice. We present
the first efficient, general-purpose algorithm for contextual bandits with
continuous, linearly structured action spaces. Our algorithm makes use of
computational oracles for (i) supervised learning, and (ii) optimization over
the action space, and achieves sample complexity, runtime, and memory
independent of the size of the action space. In addition, it is simple and
practical. We perform a large-scale empirical evaluation, and show that our
approach typically enjoys superior performance and efficiency compared to
standard baselines.
- Abstract(参考訳): 逐次意思決定における中心的な問題は、実用的で計算効率が良く、柔軟な汎用モデルの使用をサポートするアルゴリズムを開発することである。
文脈的バンディット問題に焦点をあてて、近年の進歩は、可能な選択肢(アクション)の数が小さい場合に、証明可能な効率のよいアルゴリズムを提供するが、大きな連続的なアクション空間における意思決定の保証は未解決のままであり、理論と実践の間に大きなギャップが生じる。
本稿では,連続的かつ線形に構造化された行動空間を持つコンテキスト帯域に対する,最初の効率的汎用アルゴリズムを提案する。
我々のアルゴリズムは計算オラクルを利用する
(i)指導学習、及び
(ii)アクション空間を最適化し、アクション空間のサイズに依存しないサンプルの複雑さ、実行時、メモリを実現する。
加えて、シンプルで実用的です。
大規模な経験的評価を行い,本手法は標準ベースラインよりも性能と効率が優れていることを示す。
関連論文リスト
- Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳(メタデータ) (2023-04-12T14:51:47Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳(メタデータ) (2022-10-02T05:03:38Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳(メタデータ) (2021-11-09T02:33:36Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Automated Decision-based Adversarial Attacks [48.01183253407982]
我々は、実用的で挑戦的な意思決定ベースのブラックボックスの敵意設定を考える。
この設定では、攻撃者はターゲットモデルに問い合わせるだけで最終分類ラベルを取得できる。
意思決定に基づく攻撃アルゴリズムを自動的に発見する。
論文 参考訳(メタデータ) (2021-05-09T13:15:10Z) - Structure Adaptive Algorithms for Stochastic Bandits [22.871155520200773]
構造化多武装バンディット問題のクラスにおける報酬最大化について検討する。
平均的な武器の報酬は、与えられた構造的制約を満たす。
我々は、反復的なサドルポイントソルバを用いて、インスタンス依存の低バウンドからのアルゴリズムを開発する。
論文 参考訳(メタデータ) (2020-07-02T08:59:54Z) - Adaptive Discretization for Model-Based Reinforcement Learning [10.21634042036049]
本稿では,適応離散化手法を導入し,効率的なモデルに基づくエピソード強化学習アルゴリズムを設計する。
我々のアルゴリズムは、空間の適応的な離散化を維持するために拡張された楽観的なワンステップ値反復に基づいている。
論文 参考訳(メタデータ) (2020-07-01T19:36:46Z) - Efficient Contextual Bandits with Continuous Actions [102.64518426624535]
我々は、未知の構造を持つ連続的な動作を持つ文脈的包帯に対する計算的に抽出可能なアルゴリズムを作成する。
我々の還元型アルゴリズムは、ほとんどの教師付き学習表現で構成される。
論文 参考訳(メタデータ) (2020-06-10T19:38:01Z) - Statistically Guided Divide-and-Conquer for Sparse Factorization of
Large Matrix [2.345015036605934]
統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。
第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。
第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
論文 参考訳(メタデータ) (2020-03-17T19:12:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。