論文の概要: CORe: Capitalizing On Rewards in Bandit Exploration
- arxiv url: http://arxiv.org/abs/2103.04387v1
- Date: Sun, 7 Mar 2021 16:09:37 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-09 15:57:10.232170
- Title: CORe: Capitalizing On Rewards in Bandit Exploration
- Title(参考訳): CORe:バンディット探索における報酬の活用
- Authors: Nan Wang, Branislav Kveton, Maryam Karimzadehgan
- Abstract要約: 過去の観測をランダム化して純粋に探索するバンディットアルゴリズムを提案する。
平均報酬推定における十分な楽観性は、過去の観測された報酬の分散を利用して達成される。
アルゴリズムCapitalizing On Rewards(CORe)と名付けます。
- 参考スコア(独自算出の注目度): 15.694813164770862
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a bandit algorithm that explores purely by randomizing its past
observations. In particular, the sufficient optimism in the mean reward
estimates is achieved by exploiting the variance in the past observed rewards.
We name the algorithm Capitalizing On Rewards (CORe). The algorithm is general
and can be easily applied to different bandit settings. The main benefit of
CORe is that its exploration is fully data-dependent. It does not rely on any
external noise and adapts to different problems without parameter tuning. We
derive a $\tilde O(d\sqrt{n\log K})$ gap-free bound on the $n$-round regret of
CORe in a stochastic linear bandit, where $d$ is the number of features and $K$
is the number of arms. Extensive empirical evaluation on multiple synthetic and
real-world problems demonstrates the effectiveness of CORe.
- Abstract(参考訳): 過去の観測をランダム化して純粋に探索するバンディットアルゴリズムを提案する。
特に、平均報酬推定における十分な楽観性は、過去の観測された報酬の分散を利用して達成される。
我々は報酬(コア)に乗じたアルゴリズムを命名する。
アルゴリズムは一般的であり、様々なバンディット設定に容易に適用できる。
COReの主な利点は、その探索が完全にデータに依存していることです。
外部ノイズに依存しず、パラメータチューニングなしでさまざまな問題に適応します。
我々は、$d$が特徴の数であり、$K$が腕の数である確率的な線形バンドイットにおいて、$n$-roundのCOReの後悔に、$\tilde O(d\sqrt{n\log K})$のギャップフリー境界を導出する。
複数の合成および実世界の問題に関する広範な経験的評価は、COReの有効性を示す。
関連論文リスト
- Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳(メタデータ) (2023-04-25T09:31:20Z) - Pure Exploration of Causal Bandits [9.77519365079468]
因果バンディット問題は多腕バンディットと因果推論を統合する。
オンライン学習課題:未知の因果推論分布を持つ因果グラフを与えられた場合、1つの変数に介入するか、介入しないかを選択できる。
3種類の因果モデルに対して、第一のギャップ依存完全適応純粋探索アルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-06-16T02:19:37Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳(メタデータ) (2022-02-03T21:19:36Z) - Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。
評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
論文 参考訳(メタデータ) (2021-12-13T09:48:54Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳(メタデータ) (2021-10-25T02:53:24Z) - Whittle Index for A Class of Restless Bandits with Imperfect
Observations [4.822598110892847]
我々は、最適化、強化学習、運用研究において幅広い応用分野を見出す、レスレスバンディット問題の一類を考察する。
我々のモデルでは、独立な2ドル状態のマルコフプロセスがあり、それを観察し、報酬を得るためにアクセスすることができる。
我々は,このタイプのレスレス・バンディットに対して高い性能を実現する,低複雑さのアルゴリズムを確立する。
論文 参考訳(メタデータ) (2021-08-09T05:01:19Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。