論文の概要: On the Minimax Regret for Online Learning with Feedback Graphs
- arxiv url: http://arxiv.org/abs/2305.15383v2
- Date: Sat, 28 Oct 2023 14:11:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 22:17:42.797477
- Title: On the Minimax Regret for Online Learning with Feedback Graphs
- Title（参考訳）: フィードバックグラフを用いたオンライン学習のためのMinimaxレグレクトについて
- Authors: Khaled Eldowa, Emmanuel Esposito, Tommaso Cesari, Nicol\`o
Cesa-Bianchi
- Abstract要約: 強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。
改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
- 参考スコア（独自算出の注目度）: 5.721380617450645
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we improve on the upper and lower bounds for the regret of
online learning with strongly observable undirected feedback graphs. The best
known upper bound for this problem is $\mathcal{O}\bigl(\sqrt{\alpha T\ln
K}\bigr)$, where $K$ is the number of actions, $\alpha$ is the independence
number of the graph, and $T$ is the time horizon. The $\sqrt{\ln K}$ factor is
known to be necessary when $\alpha = 1$ (the experts case). On the other hand,
when $\alpha = K$ (the bandits case), the minimax rate is known to be
$\Theta\bigl(\sqrt{KT}\bigr)$, and a lower bound $\Omega\bigl(\sqrt{\alpha
T}\bigr)$ is known to hold for any $\alpha$. Our improved upper bound
$\mathcal{O}\bigl(\sqrt{\alpha T(1+\ln(K/\alpha))}\bigr)$ holds for any
$\alpha$ and matches the lower bounds for bandits and experts, while
interpolating intermediate cases. To prove this result, we use FTRL with
$q$-Tsallis entropy for a carefully chosen value of $q \in [1/2, 1)$ that
varies with $\alpha$. The analysis of this algorithm requires a new bound on
the variance term in the regret. We also show how to extend our techniques to
time-varying graphs, without requiring prior knowledge of their independence
numbers. Our upper bound is complemented by an improved
$\Omega\bigl(\sqrt{\alpha T(\ln K)/(\ln\alpha)}\bigr)$ lower bound for all
$\alpha > 1$, whose analysis relies on a novel reduction to multitask learning.
This shows that a logarithmic factor is necessary as soon as $\alpha < K$.
- Abstract（参考訳）: 本研究では,オンライン学習の後悔に対する上層と下層の境界を,強く観察不能なフィードバックグラフを用いて改善する。
この問題の最もよく知られている上限は$\mathcal{o}\bigl(\sqrt{\alpha t\ln k}\bigr)$であり、ここで$k$はアクションの数、$\alpha$はグラフの独立数、$t$は時間軸である。
$\sqrt{\ln K}$因子は、$\alpha = 1$(専門家の場合)に必要であることが知られている。
一方、$\alpha = K$(盗賊の場合)の場合、ミニマックスレートは$\Theta\bigl(\sqrt{KT}\bigr)$、下界の$\Omega\bigl(\sqrt{\alpha T}\bigr)$は任意の$\alpha$に対して保持されることが知られている。
改良された上限 $\mathcal{o}\bigl(\sqrt{\alpha t(1+\ln(k/\alpha)))}\bigr)$ は任意の$\alpha$ に対して成立し、中間の場合を補間しながら、バンディットや専門家の下限に一致する。
この結果を証明するために、$q$-Tsallis entropyで、$\alpha$と異なる$q \in [1/2, 1)$の慎重に選択された値にFTRLを使用する。
このアルゴリズムの解析には、後悔の中の分散項に新しい境界が必要である。
また,我々の手法を時間変化グラフに拡張する方法を,その独立数の事前知識を必要とせずに示す。
我々の上限は改良された$\Omega\bigl(\sqrt{\alpha T(\ln K)/(\ln\alpha)}\bigr)$ lower bound for all $\alpha > 1$で補われ、その解析はマルチタスク学習への新たな還元に依存している。
これは、対数因子はすぐに$\alpha < k$ となることを示している。
関連論文リスト
- Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - $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) - Logarithmic Regret in Multisecretary and Online Linear Programs with
Continuous Valuations [0.0]
私は、mathbbRm$リソースに$nbetaを割り当てるリニアプログラムのシャドウ価格が、$n$顧客に対して$n$ rightarrow infty$として振舞う方法を研究します。
citesLi 2019bのオンラインリニアプログラムが$Theta(log n)$であることを証明するためにこれらの結果を使用します。
論文 参考訳（メタデータ） (2019-12-16T18:43:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。