論文の概要: No Regrets for Learning the Prior in Bandits
- arxiv url: http://arxiv.org/abs/2107.06196v1
- Date: Tue, 13 Jul 2021 15:51:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-14 14:36:43.757723
- Title: No Regrets for Learning the Prior in Bandits
- Title(参考訳): 帯域における事前学習のレグレットはない
- Authors: Soumya Basu, Branislav Kveton, Manzil Zaheer, Csaba Szepesv\'ari
- Abstract要約: $tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。
$tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
- 参考スコア(独自算出の注目度): 30.478188057004175
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose ${\tt AdaTS}$, a Thompson sampling algorithm that adapts
sequentially to bandit tasks that it interacts with. The key idea in ${\tt
AdaTS}$ is to adapt to an unknown task prior distribution by maintaining a
distribution over its parameters. When solving a bandit task, that uncertainty
is marginalized out and properly accounted for. ${\tt AdaTS}$ is a
fully-Bayesian algorithm that can be implemented efficiently in several classes
of bandit problems. We derive upper bounds on its Bayes regret that quantify
the loss due to not knowing the task prior, and show that it is small. Our
theory is supported by experiments, where ${\tt AdaTS}$ outperforms prior
algorithms and works well even in challenging real-world problems.
- Abstract(参考訳): 我々は,トンプソンサンプリングアルゴリズムである${\tt adats}$を提案する。
${\tt adats}$の鍵となるアイデアは、パラメータの分布を維持して未知のタスクの事前分布に適応させることである。
盗賊の問題を解くとき、その不確実性は疎外され、適切に説明される。
${\tt adats}$ は、バンドイット問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
我々は、そのベイズ上の上限を導き出し、そのタスクを事前に知らないために損失を定量化し、それが小さいことを示すことを後悔する。
我々の理論は実験によって支持されており、${\tt AdaTS}$は以前のアルゴリズムより優れ、現実世界の課題でもうまく機能する。
関連論文リスト
- 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) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳(メタデータ) (2023-10-28T13:01:10Z) - Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。
我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-11-16T00:10:35Z) - An Asymptotically Optimal Batched Algorithm for the Dueling Bandit
Problem [13.69077222007053]
従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。
我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。
実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
論文 参考訳(メタデータ) (2022-09-25T00:23:55Z) - 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) - Non-stationary Bandits and Meta-Learning with a Small Set of Optimal
Arms [30.024167992890916]
そこで本研究では,学習者が200ドル(約1万2000円)の帯域幅のタスクに直面する決定について検討する。
敵は各タスクの最適なアームを、M$アームのより小さな(しかし未知の)サブセットで選択することを制約される。
境界は既知のもの(非定常的メタラーニング設定)、あるいは未知のもの(非定常的バンディット設定)である。
論文 参考訳(メタデータ) (2022-02-25T22:28:01Z) - Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits
with Super Heavy-Tailed Payoffs [27.636407641546914]
実験的な中央値列の経験的平均を計算し,確率変数を推定する,新しい頑健な統計推定器を提案する。
非常に重みのある雑音であっても, 後悔の限界がほぼ最適であることを示す。
論文 参考訳(メタデータ) (2021-10-26T17:30:44Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-13T16:35:30Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic
Gradient Descent and Thompson Sampling [83.48992319018147]
プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。
この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。
本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。
過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
論文 参考訳(メタデータ) (2020-06-07T01:12:39Z) - Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial
Rewards [59.559028338399855]
我々は,行動セットと敵意の報酬を伴って睡眠中の盗賊の問題を考察する。
本稿では,EXP3にインスパイアされた新しい計算効率のよいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-14T00:41:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。