論文の概要: Non-stationary Bandits and Meta-Learning with a Small Set of Optimal
Arms
- arxiv url: http://arxiv.org/abs/2202.13001v1
- Date: Fri, 25 Feb 2022 22:28:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-01 14:17:26.733502
- Title: Non-stationary Bandits and Meta-Learning with a Small Set of Optimal
Arms
- Title（参考訳）: 小群最適腕を用いた非定常バンディットとメタラーニング
- Authors: MohammadJavad Azizi, Thang Duong, Yasin Abbasi-Yadkori, Andr\'as
Gy\"orgy, Claire Vernade, Mohammad Ghavamzadeh
- Abstract要約: そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。
敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。
境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
- 参考スコア（独自算出の注目度）: 30.024167992890916
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a sequential decision problem where the learner faces a sequence of
$K$-armed stochastic bandit tasks. The tasks may be designed by an adversary,
but the adversary is constrained to choose the optimal arm of each task in a
smaller (but unknown) subset of $M$ arms. The task boundaries might be known
(the bandit meta-learning setting), or unknown (the non-stationary bandit
setting), and the number of tasks $N$ as well as the total number of rounds $T$
are known ($N$ could be unknown in the meta-learning setting). We design an
algorithm based on a reduction to bandit submodular maximization, and show that
its regret in both settings is smaller than the simple baseline of
$\tilde{O}(\sqrt{KNT})$ that can be obtained by using standard algorithms
designed for non-stationary bandit problems. For the bandit meta-learning
problem with fixed task length $\tau$, we show that the regret of the algorithm
is bounded as $\tilde{O}(N\sqrt{M \tau}+N^{2/3})$. Under additional assumptions
on the identifiability of the optimal arms in each task, we show a bandit
meta-learning algorithm with an improved $\tilde{O}(N\sqrt{M \tau}+N^{1/2})$
regret.
- Abstract（参考訳）: 学習者がk$-armed確率的バンディットタスクのシーケンスに直面する逐次的決定問題について検討する。
タスクは敵が設計することもあるが、敵は各タスクの最適なアームをM$アームより小さい(不明)サブセットで選択することを制約される。
タスク境界は既知のもの(ビジット・メタラーニング・セッティング)、未知のもの(ビジット・メタラーニング・セッティング)、およびタスク数$N$、ラウンド数$T$が知られている(メタラーニング・セッティングではN$が未知のもの)。
我々は,帯域幅の極大化を減らしたアルゴリズムを設計し,非定常帯域幅問題のために設計された標準アルゴリズムを用いて得られる$\tilde{O}(\sqrt{KNT})$の単純なベースラインよりも,両方の設定における後悔が小さいことを示す。
固定タスク長$\tau$のバンドイットメタ学習問題に対して、アルゴリズムの後悔は$\tilde{O}(N\sqrt{M \tau}+N^{2/3})$と有界であることを示す。
各タスクにおける最適なアームの識別可能性に関する追加の仮定の下で、$\tilde{o}(n\sqrt{m \tau}+n^{1/2})$ regret を改良したバンドイットメタラーニングアルゴリズムを示す。
関連論文リスト
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - Meta-Learning for Simple Regret Minimization [34.75895755834204]
我々は,盗賊を単純に後悔させるメタラーニングフレームワークを開発した。
本稿では,ベイズ的かつ頻繁なメタ学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-25T18:56:54Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - No Regrets for Learning the Prior in Bandits [30.478188057004175]
$tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。
$tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
論文 参考訳（メタデータ） (2021-07-13T15:51:32Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。