論文の概要: Near-Optimal First-Order Regret for Bandits with Feedback Graphs
- arxiv url: http://arxiv.org/abs/2610.40861v1
- Date: Thu, 29 Oct 2026 18:37:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-02 22:05:31.472621
- Title: Near-Optimal First-Order Regret for Bandits with Feedback Graphs
- Title（参考訳）: フィードバックグラフ付き帯域のほぼ最適1次レグレット
- Abstract要約: 本研究では,固定された有向フィードバックグラフを用いて,敵の包帯に対する一次的後悔の保証について検討する。
強可観測グラフに対しては、[ACBDK15] は$widetildeO(sqrt(+1) Lstar)$ のミニマックス後悔を確立する。
ここで$$はcliqueパーティション番号を表し、$+1geq$、$Lを満たす。
- 参考スコア（独自算出の注目度）: 59.287761696290865
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study first-order regret guarantees for adversarial bandits with a fixed, known directed feedback graph. For strongly observable graphs, [ACBDK15] establishes a minimax regret of $\widetildeΘ(\sqrt{αT})$, where $α$ denotes the independence number of the graph and $T$ denotes the horizon. On the other hand, the best existing first-order bound scales as $\widetilde{O}(\sqrt{(κ+1) L^\star})$ [LLZ20], where $κ$ denotes the clique partition number, satisfying $κ+1\geqα$, and $L^\star$ denotes the cumulative loss of the best arm, leaving a gap between the graph dependence in worst-case and first-order guarantees. In this paper, we bridge this gap by obtaining an expected regret bound of $\widetilde{O}(\sqrt{αL^\star}+α)$. Our first result is an algorithm for the special case of self-aware graphs, in which every vertex has a self-loop. The algorithm combines the update of EXP3 [ACBFS02] with a sampling rule inspired by exploration by optimization [LS20]. More specifically, we construct a map whose fixed points yield sampling distributions that control the one-round regret remainder in terms of the learner's loss and the graph's independence number, which is crucial in deriving optimal first-order guarantees. We further show that a sufficiently accurate fixed point can be computed in polynomial time by a geometrically convergent iteration. Finally, we extend the algorithm to general strongly observable graphs and achieve the same $\widetilde{O}(\sqrt{αL^\star}+α)$ guarantee by adapting the two-level aggregation approach of [LLZ20].
- Abstract（参考訳）: 本研究では,固定された有向フィードバックグラフを用いて,敵の包帯に対する一次的後悔の保証について検討する。
強可観測グラフに対しては、[ACBDK15] は $\widetilde'(\sqrt{αT})$ のミニマックス後悔を確立し、$α$ はグラフの独立数を表し、$T$ は地平線を表す。
一方、最も優れた1次有界スケールは$\widetilde{O}(\sqrt{(κ+1) L^\star})$ [LLZ20] で、$κ$はcliqueパーティション数を表し、$κ+1\geqα$、$L^\star$はベストアームの累積損失を示し、最悪のケースと1次保証におけるグラフ依存の差を残す。
本稿では、このギャップを$\widetilde{O}(\sqrt{αL^\star}+α)$の既約後悔境界を得ることで埋める。
最初の結果は、全ての頂点が自己ループを持つ自己認識グラフの特殊な場合のアルゴリズムである。
このアルゴリズムは、EXP3[ACBFS02]の更新と、最適化による探索 [LS20] にインスパイアされたサンプリングルールを組み合わせる。
より具体的には、学習者の損失とグラフの独立数の観点から1ラウンドの後悔残余を制御し、最適な1次保証を導出する上で重要な、固定点がサンプリング分布を出力するマップを構築する。
さらに、幾何収束反復により多項式時間で十分正確な固定点を計算することができることを示す。
最後に、アルゴリズムを一般に観測可能なグラフに拡張し、 [LLZ20] の2レベルアグリゲーションアプローチを適用することで、同じ$\widetilde{O}(\sqrt{αL^\star}+α)$保証を達成する。
関連論文リスト
- Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits [13.08870048693199]
我々は、多武装の盗賊における一級・一級・一級の後悔の保証について研究する。
我々のアルゴリズムは、最小極最適最悪の後悔と損失依存項が$mathcalO(sqrtK Lstarlog T)$である一階保証を組み合わせる。
我々は,同一のアルゴリズムが,一意のベストアームを持つi.d.損失に対して$mathcalO(sqrtK Lstar)$ regretを伴って,ベスト・オブ・ボスの保証を達成することを示す。
論文 参考訳（メタデータ） (2026-10-29T06:28:29Z) - Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
有限水平時間同質なマルコフ決定過程に対して、$A$状態、$A$アクション、hoighty $H$、および1ドルで有界なトラジェクティブ当たりの合計報酬について、地平自由な後悔について検討する。
失敗確率$$K$はエピソード数で$tilde O(sqrtSAK+S3K)$ hides $mathsfpolyである。
論文 参考訳（メタデータ） (2026-07-22T07:42:19Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Stochastic Contextual Bandits with Graph-based Contexts [0.0]
オンライングラフ予測問題を文脈的帯域問題に一般化する。
我々のアルゴリズムは Zimmert と Seldin[AISTAT'19, JMLR'21] による最適帯域幅アルゴリズムに依存している。
論文 参考訳（メタデータ） (2023-05-02T14:51:35Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - 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) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - A Closer Look at Small-loss Bounds for Bandits with Graph Feedback [39.78074016649885]
グラフフィードバックを用いた対向多腕バンディットの低損失境界について検討する。
一般の強可観測グラフに対する最初の小さな空間境界を導出する。
また、弱可観測グラフに対する小空間境界を導出する最初の試みも行う。
論文 参考訳（メタデータ） (2020-02-02T03:48:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。