論文の概要: BanditQ -- No-Regret Learning with Guaranteed Per-User Rewards in Adversarial Environments

• arxiv url: http://arxiv.org/abs/2304.05219v1
• Date: Tue, 11 Apr 2023 13:39:47 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-12 14:43:30.397280
• Title: BanditQ -- No-Regret Learning with Guaranteed Per-User Rewards in Adversarial Environments
• Title（参考訳）: BanditQ - 対向環境におけるユーザ毎のリワードを保証したノンレグレット学習
• Authors: Abhishek Sinha
• Abstract要約: 我々は、全ての武器に対する報酬の累積率に厳しい限界を持つ敵設定における公正なオンライン予測問題を考える。 そこで我々は,BanditQと呼ばれる新たなオンライン予測ポリシーを提案し,目標レートの制約を達成しつつ,全情報設定で$O(T3/4)の償却を実現した。
• 参考スコア（独自算出の注目度）: 8.208569626646034
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Classic online prediction algorithms, such as Hedge, are inherently unfair by design, as they try to play the most rewarding arm as many times as possible while ignoring the sub-optimal arms to achieve sublinear regret. In this paper, we consider a fair online prediction problem in the adversarial setting with hard lower bounds on the rate of accrual of rewards for all arms. By combining elementary queueing theory with online learning, we propose a new online prediction policy, called BanditQ, that achieves the target rate constraints while achieving a regret of $O(T^{3/4})$ in the full-information setting. The design and analysis of BanditQ involve a novel use of the potential function method and are of independent interest.
• Abstract（参考訳）: ヘッジのような古典的なオンライン予測アルゴリズムは本質的に設計上不公平であり、最も報酬の高いアームをできるだけ何度もプレイしようとする一方で、サブ最適アームを無視してサブリニアな後悔を達成する。 本稿では,すべての腕に対する報酬の獲得率を低く抑えながら,対向的設定における公正なオンライン予測問題を考える。 本稿では,基本待ち行列理論とオンライン学習を組み合わせることで,目標レート制約を達成し,全情報設定で$O(T^{3/4})を後悔しながら,新たなオンライン予測ポリシーであるBanditQを提案する。 BanditQの設計と分析は、潜在的な関数法を新しく利用し、独立した関心を持つ。

関連論文リスト

• $\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)

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

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