論文の概要: Replicability is Asymptotically Free in Multi-armed Bandits
- arxiv url: http://arxiv.org/abs/2402.07391v1
- Date: Mon, 12 Feb 2024 03:31:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 15:42:13.557826
- Title: Replicability is Asymptotically Free in Multi-armed Bandits
- Title（参考訳）: 多腕バンドにおける再現性は漸近的に自由である
- Authors: Junpei Komiyama, Shinji Ito, Yuichi Yoshida, Souta Koshino
- Abstract要約: この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
- 参考スコア（独自算出の注目度）: 45.729105054410745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work is motivated by the growing demand for reproducible machine
learning. We study the stochastic multi-armed bandit problem. In particular, we
consider a replicable algorithm that ensures, with high probability, that the
algorithm's sequence of actions is not affected by the randomness inherent in
the dataset. We observe that existing algorithms require $O(1/\rho^2)$ times
more regret than nonreplicable algorithms, where $\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 $\rho$,
provided that the magnitude of the confidence bounds is chosen carefully. We
introduce an explore-then-commit algorithm that draws arms uniformly before
committing to a single arm. Additionally, we examine a successive elimination
algorithm that eliminates suboptimal arms at the end of each phase. To ensure
the replicability of these algorithms, we incorporate randomness into their
decision-making processes. We extend the use of successive elimination to the
linear bandit problem as well. For the analysis of these algorithms, 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(1/\rho^2)が非複製性アルゴリズムよりも後悔の度合いが高いことを観察する。
しかし、この追加コストは、与えられた$\rho$に対して時間的地平線$T$が十分に大きいときに必要であることを示す。
1つの腕にコミットする前に一様に腕を引くexplore-then-commitアルゴリズムを提案する。
さらに,各位相の終端に準最適アームを除去する逐次除去アルゴリズムについて検討する。
これらのアルゴリズムの複製性を確保するため、ランダム性を意思決定プロセスに組み込む。
また,線形バンディット問題への連続除去の利用も拡張する。
これらのアルゴリズムの解析には,非複製の可能性を制限するための原理的手法を提案する。
このアプローチは、既存の研究が暗黙的に従ったステップを解明する。
さらに、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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。