論文の概要: $\texttt{BanditQ}:$ Fair Multi-Armed Bandits with Guaranteed Rewards per
Arm
- arxiv url: http://arxiv.org/abs/2304.05219v2
- Date: Tue, 9 May 2023 13:21:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-10 20:18:41.118092
- Title: $\texttt{BanditQ}:$ Fair Multi-Armed Bandits with Guaranteed Rewards per
Arm
- Title(参考訳): $\texttt{banditq}: 腕当たりの報酬が保証された公正なマルチアームのバンディット
- Authors: Abhishek Sinha
- Abstract要約: 昔ながらのオンライン予測アルゴリズムは本質的に不公平だ。
我々は、後悔と目標レート違反のペナルティを達成しつつ、目標報酬率を達成する「texttBanditQ$」という新しいオンライン予測ポリシーを提案する。
提案手法は効率的で,公正な予測問題から標準MAB問題へのブラックボックス削減を許容する。
- 参考スコア(独自算出の注目度): 8.208569626646034
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Classic no-regret online prediction algorithms, including variants of the
Upper Confidence Bound ($\texttt{UCB}$) algorithm, $\texttt{Hedge}$, and
$\texttt{EXP3}$, are inherently unfair by design. The unfairness stems from
their very objective of playing the most rewarding arm as many times as
possible while ignoring the less rewarding ones among $N$ arms. In this paper,
we consider a fair prediction problem in the stochastic setting with hard lower
bounds on the rate of accrual of rewards for a set of arms. We study the
problem in both full and bandit feedback settings. Using queueing-theoretic
techniques in conjunction with adversarial learning, we propose a new online
prediction policy called $\texttt{BanditQ}$ that achieves the target reward
rates while achieving a regret and target rate violation penalty of
$O(T^{\frac{3}{4}}).$ In the full-information setting, the regret bound can be
further improved to $O(\sqrt{T})$ when considering the average regret over the
entire horizon of length $T$. The proposed policy is efficient and admits a
black-box reduction from the fair prediction problem to the standard MAB
problem with a carefully defined sequence of rewards. The design and analysis
of the $\texttt{BanditQ}$ policy involve a novel use of the potential function
method in conjunction with scale-free second-order regret bounds and a new
self-bounding inequality for the reward gradients, which are of independent
interest.
- Abstract(参考訳): upper confidence bound (\texttt{ucb}$) アルゴリズム、$\texttt{hedge}$、$\texttt{exp3}$の変種を含む古典的なno-regretオンライン予測アルゴリズムは、本質的に設計上不公平である。
この不公平さは、N$の腕の中で報酬の少ない腕を無視しながら、できるだけ多くの報酬を得られる腕を演奏するという、非常に目的に起因している。
本稿では,一組の武器に対する報酬の累積率に対して,厳格な下界を持つ確率的設定における公平な予測問題を考える。
フルとバンディットの両方のフィードバック設定で問題を調べます。
本稿では, 待ち行列理論と敵対学習を併用して, 目標報酬率を達成し, 後悔と目標レート違反の罰則を達成できる, $\texttt{BanditQ}$という新しいオンライン予測ポリシーを提案する。
完全な情報設定では、長さ$T$の地平線全体の平均的後悔を考えると、後悔境界はさらに$O(\sqrt{T})$に改善できる。
提案手法は効率的で,公正な予測問題から標準MAB問題へのブラックボックス還元を,慎重に定義された報酬列で許容する。
$\texttt{BanditQ}$ポリシーの設計と解析は、スケールフリーな2階後悔境界と独立な利害関係を持つ報酬勾配に対する新たな自己有界不等式と共にポテンシャル関数法を新しく使用することを含む。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳(メタデータ) (2023-05-25T14:02:12Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳(メタデータ) (2023-04-25T09:31:20Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳(メタデータ) (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳(メタデータ) (2021-02-15T19:10:52Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳(メタデータ) (2020-03-06T20:34:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。