論文の概要: On Penalization in Stochastic Multi-armed Bandits
- arxiv url: http://arxiv.org/abs/2211.08311v1
- Date: Tue, 15 Nov 2022 17:13:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-16 13:40:35.867454
- Title: On Penalization in Stochastic Multi-armed Bandits
- Title(参考訳): 確率的マルチアームバンドにおける罰則について
- Authors: Guanhua Fang, Ping Li, Gennady Samorodnitsky
- Abstract要約: 本稿では,マルチアーム・バンディット(MAB)問題の重要な変種について検討し,ペナルティ化を考慮に入れた。
フェアネス、ほぼ最適の後悔、報酬とフェアネスのトレードオフの改善など、多くのメリットを享受する難解なUPBライクなアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 22.04356596828437
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study an important variant of the stochastic multi-armed bandit (MAB)
problem, which takes penalization into consideration. Instead of directly
maximizing cumulative expected reward, we need to balance between the total
reward and fairness level. In this paper, we present some new insights in MAB
and formulate the problem in the penalization framework, where rigorous
penalized regret can be well defined and more sophisticated regret analysis is
possible. Under such a framework, we propose a hard-threshold UCB-like
algorithm, which enjoys many merits including asymptotic fairness, nearly
optimal regret, better tradeoff between reward and fairness. Both gap-dependent
and gap-independent regret bounds have been established. Multiple insightful
comments are given to illustrate the soundness of our theoretical analysis.
Numerous experimental results corroborate the theory and show the superiority
of our method over other existing methods.
- Abstract(参考訳): 本稿では,確率的マルチアーム・バンディット(MAB)問題の重要な変種について考察する。
累積的な報酬を直接最大化する代わりに、総報酬と公平度の間でバランスをとる必要があります。
本稿では,厳格に罰せられた後悔を適切に定義し,より洗練された後悔分析を可能にする,刑罰制度におけるMABの新たな洞察と問題を定式化する。
このような枠組みの下で, 漸近的公平性, ほぼ最適の後悔, 報酬と公平性の間のより良いトレードオフなど多くのメリットを享受する, 強固なucbライクなアルゴリズムを提案する。
gap-dependent と gap-independent regret bounds が確立されている。
理論的分析の健全性を説明するために、複数の洞察に富んだコメントが与えられる。
多くの実験結果が理論を裏付け、既存の方法よりも優れた方法を示している。
関連論文リスト
- An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。
本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-04-22T14:11:54Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Adversarial Robustness with Semi-Infinite Constrained Learning [177.42714838799924]
入力に対する深い学習は、安全クリティカルなドメインでの使用に関して深刻な疑問を提起している。
本稿では,この問題を緩和するために,Langevin Monte Carlo のハイブリッドトレーニング手法を提案する。
当社のアプローチは、最先端のパフォーマンスと堅牢性の間のトレードオフを軽減することができることを示す。
論文 参考訳(メタデータ) (2021-10-29T13:30:42Z) - Achieving the Pareto Frontier of Regret Minimization and Best Arm
Identification in Multi-Armed Bandits [91.8283876874947]
本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。
i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。
また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
論文 参考訳(メタデータ) (2021-10-16T17:52:32Z) - Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
問合せ予算で意思決定問題を定式化する。
我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。
我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
論文 参考訳(メタデータ) (2021-02-05T19:56:31Z) - Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax
Regret [5.1398743023989555]
我々は、各腕に関連する報酬の分布が時間変動であると仮定する非定常的マルチアーミングバンディット(MAB)問題を研究する。
提案手法は, 変動予算を満たした報酬分配系列の組に対する後悔の前提となる, 最悪の場合の後悔という観点から, 提案手法の性能を特徴付ける。
論文 参考訳(メタデータ) (2021-01-22T07:34:09Z) - A One-Size-Fits-All Solution to Conservative Bandit Problems [32.907883501286]
我々は、サンプルパス報酬制約を伴う保守的なバンディット問題(CBP)のファミリーについて研究する。
CBPに対するOne-Size-Fits-Allソリューションを提案し、その応用を3つの包括問題に提示する。
論文 参考訳(メタデータ) (2020-12-14T08:50:23Z) - Reward Biased Maximum Likelihood Estimation for Reinforcement Learning [13.820705458648233]
マルコフ連鎖の適応制御のためのRBMLE(Reward-Biased Maximum Likelihood Estimate)を提案した。
我々は、現在最先端のアルゴリズムと同様に、$mathcalO( log T)$が$T$の時間的水平線上で後悔していることを示します。
論文 参考訳(メタデータ) (2020-11-16T06:09:56Z) - 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) - Prediction with Corrupted Expert Advice [67.67399390910381]
ステップサイズを減らした古典的乗法重みアルゴリズムの変種が、良質な環境において絶え間なく後悔することを証明する。
我々の結果は、しばしば同等のFollow the Regularized Leader(FTRL)とOnline Mirror Descent(OMD)フレームワークの驚くべき相違を明らかにします。
論文 参考訳(メタデータ) (2020-02-24T14:39:55Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。