論文の概要: Residual Bootstrap Exploration for Stochastic Linear Bandit

• arxiv url: http://arxiv.org/abs/2202.11474v1
• Date: Wed, 23 Feb 2022 12:47:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-24 14:25:00.315530
• Title: Residual Bootstrap Exploration for Stochastic Linear Bandit
• Title（参考訳）: 確率線形バンディットの残留ブートストラップ探索
• Authors: Shuang Wu, Chi-Hua Wang, Yuantong Li, Guang Cheng
• Abstract要約: 線形バンディット問題に対するブートストラップに基づくオンラインアルゴリズムを提案する。 提案した textttLinReBoot は,弱い条件下では $tildeO(d sqrtn)$ sub-linear regret を保証している。
• 参考スコア（独自算出の注目度）: 33.09784550079342
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new bootstrap-based online algorithm for stochastic linear bandit problems. The key idea is to adopt residual bootstrap exploration, in which the agent estimates the next step reward by re-sampling the residuals of mean reward estimate. Our algorithm, residual bootstrap exploration for stochastic linear bandit (\texttt{LinReBoot}), estimates the linear reward from its re-sampling distribution and pulls the arm with the highest reward estimate. In particular, we contribute a theoretical framework to demystify residual bootstrap-based exploration mechanisms in stochastic linear bandit problems. The key insight is that the strength of bootstrap exploration is based on collaborated optimism between the online-learned model and the re-sampling distribution of residuals. Such observation enables us to show that the proposed \texttt{LinReBoot} secure a high-probability $\tilde{O}(d \sqrt{n})$ sub-linear regret under mild conditions. Our experiments support the easy generalizability of the \texttt{ReBoot} principle in the various formulations of linear bandit problems and show the significant computational efficiency of \texttt{LinReBoot}.
• Abstract（参考訳）: 確率線形帯域問題に対するブートストラップに基づくオンラインアルゴリズムを提案する。 重要なアイデアは、平均報酬推定の残差を再サンプリングして次のステップ報酬を見積もる、残余のブートストラップ探索を採用することである。 我々のアルゴリズムは,確率線形バンドイット(\texttt{LinReBoot})の残余ブートストラップ探索であり,リサンプリング分布から線形報酬を推定し,最も高い報酬推定値でアームを引っ張る。 特に,確率線形バンディット問題における残余ブートストラップに基づく探索機構の解明に理論的枠組みを貢献する。 重要な洞察は、ブートストラップ探索の強みは、オンライン学習モデルと残差の再サンプリング分布の協調的最適化に基づいているということである。 このような観察により、提案した \texttt{LinReBoot} が高確率の $\tilde{O}(d \sqrt{n})$ sub-linear regret を穏やかな条件下で確保できることを示すことができる。 本実験は,線形バンドイット問題の様々な定式化における \texttt{reboot} 原理の容易な一般化をサポートし, \texttt{linreboot} の計算効率を示す。

関連論文リスト

• Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
  最適輸送(OT)は、確率分布間の差を測定する機械学習分野で広く使われているツールである。 我々は、いわゆる$beta$-divergenceに付随するベータポテンシャル項でOTを正規化することを提案する。 提案アルゴリズムで計算した輸送行列は,外乱が存在する場合でも確率分布を頑健に推定するのに役立つことを実験的に実証した。
  論文  参考訳（メタデータ） (2022-12-26T18:37:28Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  エージェントが事前に特定された報酬関数を使わずに環境を徹底的に探索することを目的とした報酬のないRL問題について検討する。 関数近似の文脈でこの問題に取り組み、強力な関数近似器を活用する。 我々は、カーネルとニューラルファンクション近似器を用いた、証明可能な効率の良い報酬なしRLアルゴリズムを確立した。
  論文  参考訳（メタデータ） (2021-10-19T07:26:33Z)
• Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
  ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。 情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。 これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-05-25T10:08:41Z)
• Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards [24.983866845065926]
  我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。 本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。 提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
  論文  参考訳（メタデータ） (2020-10-24T10:44:02Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• Reward-Biased Maximum Likelihood Estimation for Linear Stochastic Bandits [16.042075861624056]
  我々は,注文最適性を証明できる新しい指標ポリシーを開発し,最先端のベンチマーク手法と競合する経験的性能を実現することを示す。 新しいポリシーは、線形バンディットに対して1プル当たりの少ない時間でこれを達成し、結果として、好意的な後悔と計算効率の両方をもたらす。
  論文  参考訳（メタデータ） (2020-10-08T16:17:53Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  我々は、最小二乗値スタイルのアルゴリズムで一般的に使用される、より標準的なベルマン誤差の概念の下での反復が、ほぼ最適値関数の学習において強力なPAC保証を提供することを示す。 そこで本稿では,任意の(線形な)報酬関数に対して,最適に近いポリシーを学習するためにどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2020-08-18T04:34:21Z)
• Residual Bootstrap Exploration for Bandit Algorithms [27.921006500629918]
  残余ブートストラップ探索(textttReBoot)という,有界あるいは非有界な報酬を持つ帯域幅アルゴリズムにおける摂動に基づく探索法を提案する。 textttReBootは、残差ベースの摂動機構を通じてデータ駆動ランダムネスを注入することで探索を実施する。 合成多武装バンディット問題における textttReBoot の評価を行い,textttReBoot は無拘束報酬に対して, textttGiro citekveton 2018garbage よりも頑健に作用することを示した。
  論文  参考訳（メタデータ） (2020-02-19T20:43:27Z)

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

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