論文の概要: Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs
- arxiv url: http://arxiv.org/abs/2210.01376v1
- Date: Tue, 4 Oct 2022 04:36:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-05 13:41:47.381940
- Title: Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs
- Title（参考訳）: 時変フィードバックグラフを用いた逆バンディットに対する高確率後悔の改善
- Authors: Haipeng Luo, Hanghang Tong, Mengxiao Zhang, Yuheng Zhang
- Abstract要約: 我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 62.52390282012508
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study high-probability regret bounds for adversarial $K$-armed bandits
with time-varying feedback graphs over $T$ rounds. For general strongly
observable graphs, we develop an algorithm that achieves the optimal regret
$\widetilde{\mathcal{O}}((\sum_{t=1}^T\alpha_t)^{1/2}+\max_{t\in[T]}\alpha_t)$
with high probability, where $\alpha_t$ is the independence number of the
feedback graph at round $t$. Compared to the best existing result [Neu, 2015]
which only considers graphs with self-loops for all nodes, our result not only
holds more generally, but importantly also removes any $\text{poly}(K)$
dependence that can be prohibitively large for applications such as contextual
bandits. Furthermore, we also develop the first algorithm that achieves the
optimal high-probability regret bound for weakly observable graphs, which even
improves the best expected regret bound of [Alon et al., 2015] by removing the
$\mathcal{O}(\sqrt{KT})$ term with a refined analysis. Our algorithms are based
on the online mirror descent framework, but importantly with an innovative
combination of several techniques. Notably, while earlier works use optimistic
biased loss estimators for achieving high-probability bounds, we find it
important to use a pessimistic one for nodes without self-loop in a strongly
observable graph.
- Abstract（参考訳）: 我々は,$t$ ラウンド以上の時間的変動フィードバックグラフを用いた,敵対的な$k$ のバンディットに対する高い確率の後悔の限界について検討した。
一般に強観測可能なグラフに対して、最適後悔値$\widetilde{\mathcal{o}}((\sum_{t=1}^t\alpha_t)^{1/2}+\max_{t\in[t]}\alpha_t)$を高い確率で達成するアルゴリズムを開発した。
グラフを全てのノードに対して自己ループで考える最も優れた結果(Neu, 2015)と比較して、我々の結果はより一般的に成り立つだけでなく、文脈的ブレイトのようなアプリケーションでは違法に大きい$\text{poly}(K)$依存を排除します。
さらに、弱可観測グラフに対する最適高確率リフレッシュバウンドを達成するアルゴリズムも開発しており、より洗練された解析で$\mathcal{O}(\sqrt{KT})$項を除去することで、[Alon et al., 2015]の最適リフレクションバウンドを改善することができる。
私たちのアルゴリズムはオンラインミラー降下フレームワークをベースにしていますが、最も重要なのはいくつかのテクニックの革新的な組み合わせです。
特に、初期の研究では、高確率境界を達成するために楽観的な偏差損失推定器を使用していたが、強可観測グラフにおいて自己ループのないノードに対して悲観的な手法を用いることが重要である。
関連論文リスト
- 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) - Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
有向フィードバックグラフが帯域幅を持つ拡張について検討する。
グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。
我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-10-09T11:21:08Z) - Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with
Feedback Graphs [34.37963000493442]
本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。
両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
論文 参考訳（メタデータ） (2022-06-02T05:01:40Z) - A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with
Feedback Graphs [21.563733343861713]
フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。
本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-01T15:14:32Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - A Closer Look at Small-loss Bounds for Bandits with Graph Feedback [39.78074016649885]
グラフフィードバックを用いた対向多腕バンディットの低損失境界について検討する。
一般の強可観測グラフに対する最初の小さな空間境界を導出する。
また、弱可観測グラフに対する小空間境界を導出する最初の試みも行う。
論文 参考訳（メタデータ） (2020-02-02T03:48:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。