論文の概要: BanditQ: Fair Bandits with Guaranteed Rewards

• arxiv url: http://arxiv.org/abs/2304.05219v3
• Date: Sun, 12 May 2024 16:05:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-15 01:51:46.778124
• Title: BanditQ: Fair Bandits with Guaranteed Rewards
• Title（参考訳）: BanditQ: Fair Bandits with Guaranteed Rewards
• Authors: Abhishek Sinha,
• Abstract要約: 古典的な非レグレットなマルチアームバンディットアルゴリズムは本質的に不公平である。 我々は、後悔と目標レート違反を容認しつつ、目標報酬率を達成する、BanditQと呼ばれる新しいオンラインポリシーを提案する。 提案手法は効率的で,公正な予測問題から標準逆MAB問題へのブラックボックス削減を許容する。
• 参考スコア（独自算出の注目度）: 10.74025233418392
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Classic no-regret multi-armed bandit algorithms, including the Upper Confidence Bound (UCB), Hedge, and EXP3, are inherently unfair by design. Their unfairness stems from their objective of playing the most rewarding arm as frequently as possible while ignoring the rest. In this paper, we consider a fair prediction problem in the stochastic setting with a guaranteed minimum rate of accrual of rewards for each arm. We study the problem in both full-information and bandit feedback settings. Combining queueing-theoretic techniques with adversarial bandits, we propose a new online policy, called BanditQ, that achieves the target reward rates while conceding a regret and target rate violation penalty of at most $O(T^{\frac{3}{4}}).$ The regret bound in the full-information setting can be further improved to $O(\sqrt{T})$ under either a monotonicity assumption or when considering time-averaged regret. The proposed policy is efficient and admits a black-box reduction from the fair prediction problem to the standard adversarial MAB problem. The analysis of the BanditQ policy involves a new self-bounding inequality, which might be of independent interest.
• Abstract（参考訳）: アッパー信頼境界(UCB)、ヘッジ(Hedge)、EXP3(EXP3)など、古典的な非レグレトなマルチ武器の盗賊アルゴリズムは本質的に不公平である。 彼らの不公平さは、最も報われる腕をできるだけ頻繁に弾きながら、残りを無視するという目的に起因している。 本稿では,各アームに対する報酬の最小化率を保証した確率的設定における公平な予測問題について考察する。 本研究は,全情報と帯域幅のフィードバック設定の両方で問題を調査する。 本稿では,待ち行列理論と敵対的盗賊を組み合わせることで,最大$O(T^{\frac{3}{4}})の後悔と目標レート違反を容認しつつ,目標報酬率を達成するBanditQという新たなオンラインポリシーを提案する。 完全な情報設定における後悔は、単調性仮定または平均的後悔を考える場合、$O(\sqrt{T})$にさらに改善することができる。 提案手法は効率的で,公正な予測問題から標準逆MAB問題へのブラックボックス削減を許容する。 BanditQポリシの分析には、独立した関心を持つ可能性のある、新たな自己拘束的不平等が含まれている。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• $\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)
• 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)

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

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