論文の概要: A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms

• arxiv url: http://arxiv.org/abs/2303.06058v1
• Date: Fri, 10 Mar 2023 16:43:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-13 14:15:49.087378
• Title: A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms
• Title（参考訳）: ランダム化されたマルチArmed Banditアルゴリズムの解析のための一般レシピ
• Authors: Dorian Baudry and Kazuya Suzuki and Junya Honda
• Abstract要約: 我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。 MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
• 参考スコア（独自算出の注目度）: 17.12382428332552
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we propose a general methodology to derive regret bounds for randomized multi-armed bandit algorithms. It consists in checking a set of sufficient conditions on the sampling probability of each arm and on the family of distributions to prove a logarithmic regret. As a direct application we revisit two famous bandit algorithms, Minimum Empirical Divergence (MED) and Thompson Sampling (TS), under various models for the distributions including single parameter exponential families, Gaussian distributions, bounded distributions, or distributions satisfying some conditions on their moments. In particular, we prove that MED is asymptotically optimal for all these models, but also provide a simple regret analysis of some TS algorithms for which the optimality is already known. We then further illustrate the interest of our approach, by analyzing a new Non-Parametric TS algorithm (h-NPTS), adapted to some families of unbounded reward distributions with a bounded h-moment. This model can for instance capture some non-parametric families of distributions whose variance is upper bounded by a known constant.
• Abstract（参考訳）: 本稿では,ランダム化マルチアームドバンディットアルゴリズムの後悔境界を導出する一般的な手法を提案する。 それは、各アームのサンプリング確率と分布の族について十分な条件のセットをチェックすることで、対数的後悔を証明する。 直接的応用として、単一パラメータ指数族、ガウス分布、有界分布、モーメント上の条件を満たす分布を含む分布の様々なモデルの下で、MED(Minimum Empirical Divergence)とTS(Thompson Sampling)の2つの有名なバンディットアルゴリズムを再検討する。 特に,MEDがこれらのモデルすべてに対して漸近的に最適であることを示すとともに,その最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。 さらに,H-モーメントを持つ非有界報酬分布の族に適応した新しい非パラメトリックTSアルゴリズム (h-NPTS) を解析することによって,本手法の関心をさらに深める。 このモデルは例えば、分散が既知の定数によって上界を持つ分布の非パラメトリックな族をキャプチャすることができる。

関連論文リスト

• On Policy Evaluation Algorithms in Distributional Reinforcement Learning [0.0]
  分散強化学習(DRL)による政策評価問題における未知の回帰分布を効率的に近似する新しいアルゴリズムのクラスを導入する。 提案したアルゴリズムの単純な例では、ワッサーシュタインとコルモゴロフ-スミルノフ距離の両方において誤差境界を証明する。 確率密度関数を持つ戻り分布の場合、アルゴリズムはこれらの密度を近似し、誤差境界は上限ノルム内で与えられる。
  論文  参考訳（メタデータ） (2024-07-19T10:06:01Z)
• Score-based generative models break the curse of dimensionality in learning a family of sub-Gaussian probability distributions [5.801621787540268]
  標準ガウス測度に対する相対密度の観点から確率分布の複雑性の概念を導入する。 パラメータが適切に有界なニューラルネットワークで対数相対密度を局所的に近似できるなら、経験的スコアマッチングによって生成された分布はターゲット分布を近似する。 本証明の重要な要素は,前処理に付随する真のスコア関数に対する次元自由深部ニューラルネットワーク近似率を導出することである。
  論文  参考訳（メタデータ） (2024-02-12T22:02:23Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-18T14:34:21Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。 我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
  論文  参考訳（メタデータ） (2020-11-17T05:41:50Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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