論文の概要: Replicability is Asymptotically Free in Multi-armed Bandits

• arxiv url: http://arxiv.org/abs/2402.07391v2
• Date: Fri, 10 Jan 2025 21:24:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:28:45.133203
• Title: Replicability is Asymptotically Free in Multi-armed Bandits
• Title（参考訳）: 多腕バンドにおける再現性は漸近的に自由である
• Authors: Junpei Komiyama, Shinji Ito, Yuichi Yoshida, Souta Koshino,
• Abstract要約: 我々は,アルゴリズムの動作シーケンスがデータセットに固有のランダム性の影響を受けないことを高い確率で保証する,レプリカブルなマルチアームバンディットアルゴリズムを考察する。 非複製の確率を制限するための原則的アプローチを提案する。
• 参考スコア（独自算出の注目度）: 41.86005698892541
• License:
• Abstract: We consider a replicable stochastic multi-armed bandit algorithm that ensures, with high probability, that the algorithm's sequence of actions is not affected by the randomness inherent in the dataset. Replicability allows third parties to reproduce published findings and assists the original researcher in applying standard statistical tests. We observe that existing algorithms require $O(K^2/\rho^2)$ times more regret than nonreplicable algorithms, where $K$ is the number of arms and $\rho$ is the level of nonreplication. However, we demonstrate that this additional cost is unnecessary when the time horizon $T$ is sufficiently large for a given $K, \rho$, provided that the magnitude of the confidence bounds is chosen carefully. Therefore, for a large $T$, our algorithm only suffers $K^2/\rho^2$ times smaller amount of exploration than existing algorithms. To ensure the replicability of the proposed algorithms, we incorporate randomness into their decision-making processes. We propose a principled approach to limiting the probability of nonreplication. This approach elucidates the steps that existing research has implicitly followed. Furthermore, we derive the first lower bound for the two-armed replicable bandit problem, which implies the optimality of the proposed algorithms up to a $\log\log T$ factor for the two-armed case.
• Abstract（参考訳）: 我々は,アルゴリズムの動作列がデータセットに固有のランダム性の影響を受けないことを高い確率で保証する,複製可能な確率的マルチアームバンディットアルゴリズムを考察する。 リプリケータビリティにより、第三者が公表された発見を再現し、標準統計テストの適用において元の研究者を支援することができる。 既存のアルゴリズムでは、$O(K^2/\rho^2)$は非複製可能アルゴリズムの2倍の後悔が必要であり、$K$はアームの数、$\rho$は非複製のレベルである。 しかし、この追加コストは、与えられた$K, \rho$に対して時間的地平線$T$が十分に大きいときに必要であることを示す。 したがって、大規模な$T$の場合、我々のアルゴリズムは既存のアルゴリズムよりも少ない探索量であるK^2/\rho^2$のみを被る。 提案アルゴリズムの複製性を確保するため,ランダム性を意思決定プロセスに組み込む。 非複製の確率を制限するための原則的アプローチを提案する。 このアプローチは、既存の研究が暗黙的に従ってきたステップを解明する。 さらに、2本腕のレプリカブルバンディット問題に対する最初の下界を導出し、提案アルゴリズムの最適性を2本腕の場合に最大$\log\log T$ factorまで求める。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions [91.8283876874947]
  我々は,T段の固定予算設定において,敵対的腐敗を伴う連続的包帯に対する最適な腕識別(BAI)問題を考察した。 我々は, 汚職の量に依存しない新しいランダム化アルゴリズム, Probabilistic Shrinking($u$) (PSS($u$)) を設計する。 CPS が十分に大きいとき、BAI 確率を$Trightarrow infty$ として達成できるアルゴリズムは存在しない。
  論文  参考訳（メタデータ） (2020-10-15T17:34:26Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms [0.966840768820136]
  文脈的帯域設定におけるモデル選択タスクについて検討する。 我々の提案は、一般的なブラックボックス・コンテクスト・バンディットアルゴリズムの収集に適応する最初のものである。
  論文  参考訳（メタデータ） (2020-06-05T18:55:16Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack [41.060507338755784]
  本稿では,各ラウンドで敵が一定の確率で攻撃する攻撃モデルについて検討する。 そこで我々は, 中央値および探索支援UPBアルゴリズム(med-E-UCB)と中央値の$epsilon$-greedyアルゴリズム(med-$epsilon$-greedy)を提案する。 どちらのアルゴリズムも上記の攻撃モデルに対して確実に堅牢である。より具体的には、どちらのアルゴリズムも$mathcalO(log T)$ pseudo-regret (i.e.)を達成することを示す。
  論文  参考訳（メタデータ） (2020-02-17T19:21:08Z)

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

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