論文の概要: Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with
Feedback Graphs
- arxiv url: http://arxiv.org/abs/2206.00873v1
- Date: Thu, 2 Jun 2022 05:01:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-03 14:27:52.208649
- Title: Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with
Feedback Graphs
- Title（参考訳）: フィードバックグラフを用いたオンライン学習のためのほぼ最適両世界の最適アルゴリズム
- Authors: Shinji Ito, Taira Tsuchiya, Junya Honda
- Abstract要約: 本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。
両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
- 参考スコア（独自算出の注目度）: 34.37963000493442
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study considers online learning with general directed feedback graphs.
For this problem, we present best-of-both-worlds algorithms that achieve nearly
tight regret bounds for adversarial environments as well as poly-logarithmic
regret bounds for stochastic environments. As Alon et al. [2015] have shown,
tight regret bounds depend on the structure of the feedback graph:
\textit{strongly observable} graphs yield minimax regret of $\tilde{\Theta}(
\alpha^{1/2} T^{1/2} )$, while \textit{weakly observable} graphs induce minimax
regret of $\tilde{\Theta}( \delta^{1/3} T^{2/3} )$, where $\alpha$ and
$\delta$, respectively, represent the independence number of the graph and the
domination number of a certain portion of the graph. Our proposed algorithm for
strongly observable graphs has a regret bound of $\tilde{O}( \alpha^{1/2}
T^{1/2} ) $ for adversarial environments, as well as of $ {O} ( \frac{\alpha
(\ln T)^3 }{\Delta_{\min}} ) $ for stochastic environments, where
$\Delta_{\min}$ expresses the minimum suboptimality gap. This result resolves
an open question raised by Erez and Koren [2021]. We also provide an algorithm
for weakly observable graphs that achieves a regret bound of $\tilde{O}(
\delta^{1/3}T^{2/3} )$ for adversarial environments and poly-logarithmic regret
for stochastic environments. The proposed algorithms are based on the
follow-the-perturbed-leader approach combined with newly designed update rules
for learning rates.
- Abstract（参考訳）: 本研究では,一般有向フィードバックグラフを用いたオンライン学習について考察する。
この問題に対して,確率的環境に対する多対数的後悔境界だけでなく,敵対的環境に対するほぼ厳密な後悔境界を実現するベスト・オブ・ザ・ワールドズアルゴリズムを提案する。
alon et alのように。
2015] は、厳密な後悔の限界がフィードバックグラフの構造に依存することを示した: \textit{strongly observable} グラフは、$\tilde{\theta}( \alpha^{1/2} t^{1/2} )$ のミニマックス後悔を与えるが、 \textit{weakly observable} グラフは$\tilde{\theta}( \delta^{1/3} t^{2/3} )$ のミニマックス後悔を誘導する。
強可観測グラフに対する提案アルゴリズムは、逆向き環境に対しては$\tilde{O}( \alpha^{1/2} T^{1/2} )$、確率的環境においては$ {O} ( \frac{\alpha (\ln T)^3 }{\Delta_{\min}} ) $ の残差を持つ。
この結果は、erez氏とkoren氏[2021]によって提起されたオープン質問を解決している。
また,逆境環境に対して$\tilde{o}( \delta^{1/3}t^{2/3})$と確率環境に対する多対数的後悔を得られる弱可観測グラフのアルゴリズムを提供する。
提案アルゴリズムは、学習率の更新ルールを新たに設計した後続のリーダアプローチに基づいている。
関連論文リスト
- Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
有向フィードバックグラフが帯域幅を持つ拡張について検討する。
グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。
我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-10-09T11:21:08Z) - 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) - Simultaneously Learning Stochastic and Adversarial Bandits with General
Graph Feedback [15.429356827868514]
一般フィードバックグラフの探索と活用のための新たなトレードオフ機構を導入する。
提案アルゴリズムは,対数設定において,$mathrmpoly-designed log T$ regretを同時に達成する。
これは、一般のフィードバックグラフに対する世界で初めての最良の結果である。
論文 参考訳（メタデータ） (2022-06-16T04:21:27Z) - 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) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。