論文の概要: 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の設計と分析は、潜在的な関数法を新しく利用し、独立した関心を持つ。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。