論文の概要: Minimax Policy for Heavy-tailed Bandits
- arxiv url: http://arxiv.org/abs/2007.10493v2
- Date: Wed, 18 Nov 2020 01:34:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 12:54:19.367853
- Title: Minimax Policy for Heavy-tailed Bandits
- Title(参考訳): ヘビーテールバンドのミニマックス政策
- Authors: Lai Wei and Vaibhav Srivastava
- Abstract要約: 我々は、飽和経験平均を用いて、ガウス以下の報酬分布に対するミニマックスポリシー MOSS を修正し、ロバスト MOSS と呼ばれる新しいアルゴリズムを設計する。
報酬分布に対する1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1。
- 参考スコア(独自算出の注目度): 10.203602318836444
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the stochastic Multi-Armed Bandit (MAB) problem under worst-case
regret and heavy-tailed reward distribution. We modify the minimax policy MOSS
for the sub-Gaussian reward distribution by using saturated empirical mean to
design a new algorithm called Robust MOSS. We show that if the moment of order
$1+\epsilon$ for the reward distribution exists, then the refined strategy has
a worst-case regret matching the lower bound while maintaining a
distribution-dependent logarithm regret.
- Abstract(参考訳): 我々は,最悪の後悔と重み付き報酬分布の下で,確率的マルチアーマッド・バンドイット(MAB)問題を考察した。
我々は、飽和経験平均を用いて、ガウス以下の報酬分布に対するミニマックスポリシー MOSS を修正し、ロバスト MOSS と呼ばれる新しいアルゴリズムを設計する。
報酬分布に対する1+\epsilon$の注文がある場合、洗練された戦略は、分布依存の対数後悔を維持しながら、下限に合致する最悪のケースの後悔を持つ。
関連論文リスト
- Forced Exploration in Bandit Problems [12.13966146283641]
マルチアームバンディット(MAB)は古典的なシーケンシャルな決定問題である。
本稿では,報酬分布に関する情報を使わずに実装可能なマルチアームバンディットアルゴリズムを設計することを目的とする。
論文 参考訳(メタデータ) (2023-12-12T14:00:29Z) - $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。
AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
論文 参考訳(メタデータ) (2023-10-04T17:11:15Z) - Implicitly normalized forecaster with clipping for linear and non-linear
heavy-tailed multi-armed bandits [85.27420062094086]
Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。
重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。
INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
論文 参考訳(メタデータ) (2023-05-11T12:00:43Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳(メタデータ) (2023-04-25T09:31:20Z) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳(メタデータ) (2022-06-07T18:08:21Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-07-13T17:37:21Z) - Regret Minimization in Heavy-Tailed Bandits [12.272975892517039]
マルチアームバンディット設定における古典的後悔最小化問題を再考する。
本稿では,1次項における下界を正確に一致させる最適アルゴリズムを提案する。
我々の指数は、よく知られたトリミングまたはトリミングされた経験的平均推定値よりも速く集中していることを示す。
論文 参考訳(メタデータ) (2021-02-07T07:46:24Z) - Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax
Regret [5.1398743023989555]
我々は、各腕に関連する報酬の分布が時間変動であると仮定する非定常的マルチアーミングバンディット(MAB)問題を研究する。
提案手法は, 変動予算を満たした報酬分配系列の組に対する後悔の前提となる, 最悪の場合の後悔という観点から, 提案手法の性能を特徴付ける。
論文 参考訳(メタデータ) (2021-01-22T07:34:09Z) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳(メタデータ) (2020-06-22T16:06:25Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。