論文の概要: Reproducible Bandits

• arxiv url: http://arxiv.org/abs/2210.01898v1
• Date: Tue, 4 Oct 2022 20:36:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-06 14:27:48.275110
• Title: Reproducible Bandits
• Title（参考訳）: 再現可能なバンド
• Authors: Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, Grigoris Velegkas
• Abstract要約: バンディット環境におけるポリシーは、2つの異なる実行において全く同じ腕列を高い確率で引き出すと再現可能と呼ばれる。 再現可能なポリシが存在するだけでなく、時間的地平線の観点から、ほぼ同じ(再現不可能な)後悔境界を達成することを示す。 以上の結果から,無作為化が探索・探索トレードオフに不可欠であるにもかかわらず,同一の腕を2回の異なるラウンドで引き抜いて最適なバランスをとれることが示唆された。
• 参考スコア（独自算出の注目度）: 95.8830340560603
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we introduce the notion of reproducible policies in the context of stochastic bandits, one of the canonical problems in interactive learning. A policy in the bandit environment is called reproducible if it pulls, with high probability, the \emph{exact} same sequence of arms in two different and independent executions (i.e., under independent reward realizations). We show that not only do reproducible policies exist, but also they achieve almost the same optimal (non-reproducible) regret bounds in terms of the time horizon. More specifically, in the stochastic multi-armed bandits setting, we develop a policy with an optimal problem-dependent regret bound whose dependence on the reproducibility parameter is also optimal. Similarly, for stochastic linear bandits (with finitely and infinitely many arms) we develop reproducible policies that achieve the best-known problem-independent regret bounds with an optimal dependency on the reproducibility parameter. Our results show that even though randomization is crucial for the exploration-exploitation trade-off, an optimal balance can still be achieved while pulling the exact same arms in two different rounds of executions.
• Abstract（参考訳）: 本稿では,対話型学習における標準問題の一つとして,確率的バンディットの文脈における再現可能なポリシーの概念を紹介する。 バンディット環境におけるポリシーは、2つの異なる独立した実行(すなわち、独立報酬実現の下で)において、高い確率で \emph{exact} の同じ武器列を引くと再現可能と呼ばれる。 我々は、再現可能なポリシーが存在するだけでなく、時間軸の観点でほぼ同じ最適(非再現可能)の後悔の限界を達成することを示した。 より具体的には、確率的マルチアームバンディット設定において、再現性パラメータへの依存も最適である最適な問題依存リセット境界を持つポリシーを開発する。 同様に、確率線型包帯(有限かつ無限の腕を持つ)に対しては、再現可能性パラメータに最適な依存を持つ最もよく知られた問題非依存の後悔境界を達成する再現可能なポリシーを開発する。 以上の結果から,探索・探索のトレードオフにはランダム化が不可欠であるが,2つの異なる実行ラウンドで全く同じアームを引っ張りながら,最適なバランスが達成できることが示された。

関連論文リスト

• Information Capacity Regret Bounds for Bandits with Mediator Feedback [55.269551124587224]
  我々は,政策セットの複雑さに対する情報理論尺度として,政策セットの容量を導入する。 古典的なEXP4アルゴリズムを採用することで、ポリシーセットの容量に応じて、新たな後悔の限界を提供する。 ポリシーセットファミリの選択については、キャパシティと同じようなスケールで、ほぼ整合性の低い境界を証明します。
  論文  参考訳（メタデータ） (2024-02-15T19:18:47Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Best of Both Worlds Model Selection [39.211071446838474]
  ネストされた政策クラスが存在する場合のバンディットシナリオにおけるモデル選択の問題について検討する。 私たちのアプローチでは、各ベース学習者は、保持するかもしれないし持たないかもしれない後悔の候補を伴わなければならない。 これらは、(線形)バンディットのシナリオでモデル選択を行いながら、(確率的および敵対的)双方の保証を最大限に達成する最初の理論的結果である。
  論文  参考訳（メタデータ） (2022-06-29T20:57:30Z)
• The Countable-armed Bandit with Vanishing Arms [8.099977107670918]
  我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。 非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
  論文  参考訳（メタデータ） (2021-10-23T02:47:55Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards [10.66048003460524]
  本稿では,複数の演奏とマルコフ報酬を含む古典的マルチアームバンディット問題の拡張について検討する。 この問題に対処するために、各段階において、全てのアームのサンプル手段からの情報と、ラウンドロビン方式で選択された単一アームのクルバック・リーバー上信頼境界とを結合する適応的アロケーションルールを検討する。
  論文  参考訳（メタデータ） (2020-01-30T08:09:01Z)

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

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