論文の概要: A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
- arxiv url: http://arxiv.org/abs/2002.00315v2
- Date: Tue, 23 Jun 2020 02:06:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-04 19:48:08.838070
- Title: A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
- Title（参考訳）: グラフフィードバックによるバンディットのスモールロス境界について
- Authors: Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang
- Abstract要約: グラフフィードバックを用いた対向多腕バンディットの低損失境界について検討する。
一般の強可観測グラフに対する最初の小さな空間境界を導出する。
また、弱可観測グラフに対する小空間境界を導出する最初の試みも行う。
- 参考スコア（独自算出の注目度）: 39.78074016649885
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study small-loss bounds for adversarial multi-armed bandits with graph
feedback, that is, adaptive regret bounds that depend on the loss of the best
arm or related quantities, instead of the total number of rounds. We derive the
first small-loss bound for general strongly observable graphs, resolving an
open problem of Lykouris et al. (2018). Specifically, we develop an algorithm
with regret $\mathcal{\tilde{O}}(\sqrt{\kappa L_*})$ where $\kappa$ is the
clique partition number and $L_*$ is the loss of the best arm, and for the
special case of self-aware graphs where every arm has a self-loop, we improve
the regret to $\mathcal{\tilde{O}}(\min\{\sqrt{\alpha T}, \sqrt{\kappa L_*}\})$
where $\alpha \leq \kappa$ is the independence number. Our results
significantly improve and extend those by Lykouris et al. (2018) who only
consider self-aware undirected graphs.
Furthermore, we also take the first attempt at deriving small-loss bounds for
weakly observable graphs. We first prove that no typical small-loss bounds are
achievable in this case, and then propose algorithms with alternative
small-loss bounds in terms of the loss of some specific subset of arms. A
surprising side result is that $\mathcal{\tilde{O}}(\sqrt{T})$ regret is
achievable even for weakly observable graphs as long as the best arm has a
self-loop.
Our algorithms are based on the Online Mirror Descent framework but require a
suite of novel techniques that might be of independent interest. Moreover, all
our algorithms can be made parameter-free without the knowledge of the
environment.
- Abstract（参考訳）: 本研究では, 弾数ではなく, 最善の腕や関連量の損失に依存する適応的後悔境界を用いて, 敵の多腕バンディットに対する小損失境界について検討した。
一般の強可観測グラフに対する最初の小さな空間境界を導出し、Lykouris et al. (2018) の開問題を解く。
具体的には、後悔する$\mathcal{\tilde{O}}(\sqrt{\kappa L_*})$で、$\kappa$はcliqueパーティション数であり、$L_*$はベストアームの損失であり、各アームが自己ループを持つ特殊な自己認識グラフの場合、$\mathcal{\tilde{O}}(\min\{\sqrt{\alpha T}, \sqrt{\kappa L_*}\})$で、後悔する$\mathcal{\tilde{O}}(\min\{\sqrt{\alpha T}, \sqrt{\kappa L_*}\})$で、$\alpha \leq \kappa$は独立数である。
我々の結果はLykouris et al. (2018) によって改善され拡張され、自己認識無向グラフのみを考える。
さらに,弱可観測グラフに対する小損失境界を導出する最初の試みも行った。
この場合、我々はまず、典型的な小損失境界が達成可能でないことを証明し、次に特定のアームのサブセットの損失という観点で、別の小損失境界を持つアルゴリズムを提案する。
驚くべき結果として、$\mathcal{\tilde{o}}(\sqrt{t})$ regretは、最良のアームが自己ループを持つ限り、弱い可観測グラフでも達成可能である。
当社のアルゴリズムはオンラインミラー Descent フレームワークをベースとしていますが,独立した興味を持つ可能性のある,新しいテクニックのスイートが必要です。
さらに、我々のアルゴリズムは環境の知識を使わずにパラメータフリーにすることができる。
関連論文リスト
- On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。
その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
論文 参考訳（メタデータ） (2023-07-14T10:38:30Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - 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) - Understanding Bandits with Graph Feedback [0.0]
一般的な後悔すべき上界$Oleft(left(delta*log |V|right)frac13Tfrac23right)$と下界$Omegaleft(left(delta*/alpharight)frac13Tfrac23right)$を証明します。
いくつかのグラフの特別な族に対して、$left(log |V|right)frac13$ factorを排除できることを示す。
論文 参考訳（メタデータ） (2021-05-29T09:35:28Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。