論文の概要: $\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階後悔境界と独立な利害関係を持つ報酬勾配に対する新たな自己有界不等式と共にポテンシャル関数法を新しく使用することを含む。
関連論文リスト
- $\alpha$-Fair Contextual Bandits [10.74025233418392]
コンテキストバンディットアルゴリズムは、レコメンデータシステム、臨床試験、最適なポートフォリオ選択など、多くのアプリケーションの中核にある。
文脈的バンディット文学で研究される最も一般的な問題の1つは、各ラウンドにおける報酬の合計を最大化することである。
本稿では,大域的な$alpha$-fairtextual Con Bandits問題を考える。
論文 参考訳（メタデータ） (2023-10-22T03:42:59Z) - Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
論文 参考訳（メタデータ） (2023-06-12T12:35:16Z) - Contextual bandits with concave rewards, and an application to fair
ranking [108.48223948875685]
CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。
我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。
推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
論文 参考訳（メタデータ） (2022-10-18T16:11:55Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳（メタデータ） (2022-03-18T08:03:20Z) - Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits [66.02233330016435]
後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-12T03:24:57Z) - 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) - 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) - Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。
我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
論文 参考訳（メタデータ） (2020-03-05T21:29:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。