論文の概要: Regret Analysis of Sleeping Competing Bandits
- arxiv url: http://arxiv.org/abs/2603.19700v1
- Date: Fri, 20 Mar 2026 07:11:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-23 19:48:39.035977
- Title: Regret Analysis of Sleeping Competing Bandits
- Title（参考訳）: 睡眠競合バンドのレグレト解析
- Authors: Shinnosuke Uba, Yutaro Yamaguchi,
- Abstract要約: 本稿では, 合理的な仮定の下で, $mathrmOleft(NKlog T_i/2right)$の後悔境界を同時に達成するアルゴリズムを提案する。
また、同じ仮定で$mathrmleft(N(K-N+1)log T_i/2 right)$の後悔の低い下界も提供する。
- 参考スコア（独自算出の注目度）: 0.2291770711277359
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Competing Bandits framework is a recently emerging area that integrates multi-armed bandits in online learning with stable matching in game theory. While conventional models assume that all players and arms are constantly available, in real-world problems, their availability can vary arbitrarily over time. In this paper, we formulate this setting as Sleeping Competing Bandits. To analyze this problem, we naturally extend the regret definition used in existing competing bandits and derive regret bounds for the proposed model. We propose an algorithm that simultaneously achieves an asymptotic regret bound of $\mathrm{O}\left(NK\log T_{i}/Δ^2\right)$ under reasonable assumptions, where $N$ is the number of players, $K$ is the number of arms, $T_{i}$ is the number of rounds of each player $p_i$, and $Δ$ is the minimum reward gap. We also provide a regret lower bound of $\mathrmΩ\left( N(K-N+1)\log T_{i}/Δ^2 \right)$ under the same assumptions. This implies that our algorithm is asymptotically optimal in the regime where the number of arms $K$ is relatively larger than the number of players $N$.
- Abstract（参考訳）: Competing Banditsフレームワークは、オンライン学習にマルチアームバンディットと、ゲーム理論における安定したマッチングを統合した、最近登場した分野である。
従来のモデルは、すべてのプレイヤーとアームが常に利用可能であると仮定しているが、現実の問題では、その可用性は時間とともに任意に変化する可能性がある。
本稿では,この設定をSleeping Competing Banditsとして定式化する。
この問題を解析するために、既存の競合する帯域で使われる後悔の定義を自然に拡張し、提案モデルに対する後悔境界を導出する。
妥当な仮定の下では、asymsymotic regret bound of $\mathrm{O}\left(NK\log T_{i}/Δ^2\right)$, $N$ is the number of player, $K$ is the number of arms, $T_{i}$ is the number of rounds of each player $p_i$, $Δ$ is the least reward gap。
また、同じ仮定で$\mathrmΩ\left(N(K-N+1)\log T_{i}/Δ^2 \right)$の後悔の低い下界も提供する。
これは、我々のアルゴリズムが、腕数$K$がプレイヤー数$N$よりも比較的大きい体制において漸近的に最適であることを意味する。
関連論文リスト
- Corrupted Learning Dynamics in Games [62.73758165845971]
すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。
本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
論文 参考訳（メタデータ） (2024-12-10T02:23:44Z) - An Asymptotically Optimal Batched Algorithm for the Dueling Bandit
Problem [13.69077222007053]
従来のマルチアームバンディット問題(英語版)のバリエーションである$K$のデュエルリングバンディット問題(英語版)について検討し、フィードバックをペア比較の形で得られる。
我々は、$O(K2log(K)) + O(Klog(T))$ in $O(log(T))$ rounds を後悔する。
実世界の様々なデータセットに対する計算実験において、$O(log(T))$ラウンドを用いたアルゴリズムが完全に同じ性能を達成することが観察された。
論文 参考訳（メタデータ） (2022-09-25T00:23:55Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
アルゴリズムが「割引なし」の場合、予想される遊びの割引エルゴジック分布が粗相関平衡(CCE)の集合に収束することを示した。
ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
論文 参考訳（メタデータ） (2021-03-08T05:15:31Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Blocking Bandits [33.14975454724348]
我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。
全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。
我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2019-07-27T20:42:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。