論文の概要: Model Selection in Contextual Stochastic Bandit Problems

• arxiv url: http://arxiv.org/abs/2003.01704v3
• Date: Sun, 4 Dec 2022 18:34:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-26 22:08:11.227567
• Title: Model Selection in Contextual Stochastic Bandit Problems
• Title（参考訳）: 文脈確率帯域問題におけるモデル選択
• Authors: Aldo Pacchiano, My Phan, Yasin Abbasi-Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, Csaba Szepesvari
• Abstract要約: 基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
• 参考スコア（独自算出の注目度）: 51.94632035240787
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega(\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.
• Abstract（参考訳）: 確率環境における帯域モデル選択について検討する。 提案手法は,候補ベースアルゴリズムを選択するメタアルゴリズムに依存する。 本稿では,基本アルゴリズムの一般クラスと異なる種類の対向メタアルゴリズムを扱うメタアルゴリズムの抽象化を開発する。 提案手法は,確率的文脈的帯域幅問題に対する最適$O(\sqrt{T})$モデル選択保証を,最適基底アルゴリズムが高い確率後悔保証を満たす限り得られるような,バンディットアルゴリズムの新規で汎用的なスムージング変換に依存する。 基本アルゴリズムの1つが$O(\log T)$後悔している場合でも、一般に、モデル選択において$Omega(\sqrt{T})$後悔よりも良くなることは不可能である。 本手法を用いて,不特定な線形文脈バンディット,未知次元の線形バンディット,未知特徴マップを用いた強化学習など,様々な問題におけるモデル選択に対処する。 本アルゴリズムは,メタアルゴリズム学習率の調整に最適なベース後悔の知識を必要とする。 このような事前の知識がなければ、メタアルゴリズムは最適な基本的後悔よりも大きな後悔を被る可能性がある。

関連論文リスト

• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
  モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。 我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Regret Bound Balancing and Elimination for Model Selection in Bandits and RL [34.15978290083909]
  バンディットおよび強化学習問題におけるアルゴリズムの簡易モデル選択手法を提案する。 我々は、このアプローチの総後悔は、最も有効な候補者の後悔の回数が乗算的要因であることを証明します。 線形バンディットのモデル選択における最近の取り組みとは違って,我々のアプローチは,敵の環境によってコンテキスト情報が生成されるケースをカバーできるほど多用途である。
  論文  参考訳（メタデータ） (2020-12-24T00:53:42Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)

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

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