論文の概要: From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits

• arxiv url: http://arxiv.org/abs/2111.09724v1
• Date: Thu, 18 Nov 2021 14:34:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-19 13:57:43.915703
• Title: From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits
• Title（参考訳）: 最適性からロバスト性:確率帯域におけるディリクレサンプリング戦略
• Authors: Dorian Baudry (CRIStAL, Scool, CNRS), Patrick Saux (CRIStAL, Scool), Odalric-Ambrym Maillard (CRIStAL, Scool)
• Abstract要約: 本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The stochastic multi-arm bandit problem has been extensively studied under standard assumptions on the arm's distribution (e.g bounded with known support, exponential family, etc). These assumptions are suitable for many real-world problems but sometimes they require knowledge (on tails for instance) that may not be precisely accessible to the practitioner, raising the question of the robustness of bandit algorithms to model misspecification. In this paper we study a generic Dirichlet Sampling (DS) algorithm, based on pairwise comparisons of empirical indices computed with re-sampling of the arms' observations and a data-dependent exploration bonus. We show that different variants of this strategy achieve provably optimal regret guarantees when the distributions are bounded and logarithmic regret for semi-bounded distributions with a mild quantile condition. We also show that a simple tuning achieve robustness with respect to a large class of unbounded distributions, at the cost of slightly worse than logarithmic asymptotic regret. We finally provide numerical experiments showing the merits of DS in a decision-making problem on synthetic agriculture data.
• Abstract（参考訳）: 確率的マルチアームバンドイット問題は、腕の分布に関する標準的な仮定(例えば、既知の支持、指数族など)の下で広く研究されている。 これらの仮定は多くの実世界の問題に適しているが、実践者が正確にアクセスできない知識(例えばテール)を必要とすることがあるため、誤った特定をモデル化するためにバンディットアルゴリズムの頑健さが問題となる。 本稿では,両腕の観測値の再サンプリングとデータ依存探索ボーナスで計算された経験指標のペアワイズ比較に基づいて,汎用ディリクレサンプリング(ds)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに最適の後悔を保証し、穏やかな質的条件を持つ半有界分布に対して対数的後悔を与える。 また、単純なチューニングは、対数的漸近的後悔よりもわずかに悪いコストで、大きな非有界分布のクラスに対してロバスト性を達成することを示す。 合成農業データにおける決定問題におけるDSのメリットを示す数値実験を行った。

関連論文リスト

• Distribution Estimation under the Infinity Norm [19.997465098927858]
  我々は$ell_infty$ノルムの下で離散確率分布を推定するための新しい境界を示す。 我々のデータ依存収束保証は、現在知られている結果に対して最大極大推定器を著しく改善する。
  論文  参考訳（メタデータ） (2024-02-13T12:49:50Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Distributionally Robust Skeleton Learning of Discrete Bayesian Networks [9.46389554092506]
  我々は、潜在的に破損したデータから一般的な離散ベイズネットワークの正確なスケルトンを学習する問題を考察する。 本稿では,有界ワッサーシュタイン距離(KL)における分布群に対する最も有害なリスクを,経験的分布へのKL分散を最適化することを提案する。 本稿では,提案手法が標準正規化回帰手法と密接に関連していることを示す。
  論文  参考訳（メタデータ） (2023-11-10T15:33:19Z)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [16.114012813668932]
  我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。 MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
  論文  参考訳（メタデータ） (2023-03-10T16:43:48Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Optimal Fixed-Budget Best Arm Identification using the Augmented Inverse Probability Estimator in Two-Armed Gaussian Bandits with Unknown Variances [27.122181278234617]
  両腕のガウスバンドにおける固定予算ベストアーム識別問題について検討する。 本稿では,アームドローの目標配置確率を推定し,ランダム化サンプリング(RS)を用いたサンプリングルールを含む戦略を提案する。 提案手法は,サンプルサイズが無限大になり,両腕間のギャップがゼロとなる場合に,不可視的に最適であることを示す。
  論文  参考訳（メタデータ） (2022-01-12T13:38:33Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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