論文の概要: Expected Worst Case Regret via Stochastic Sequential Covering
- arxiv url: http://arxiv.org/abs/2209.04417v1
- Date: Fri, 9 Sep 2022 17:31:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-12 12:58:30.953839
- Title: Expected Worst Case Regret via Stochastic Sequential Covering
- Title（参考訳）: 確率的シーケンシャルカバーによる最悪の場合の後悔
- Authors: Changlong Wu, Mohsen Heidari, Ananth Grama, Wojciech Szpankowski
- Abstract要約: 我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。
そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。
対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
- 参考スコア（独自算出の注目度）: 14.834625066344582
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of sequential prediction and online minimax regret with
stochastically generated features under a general loss function. We introduce a
notion of expected worst case minimax regret that generalizes and encompasses
prior known minimax regrets. For such minimax regrets we establish tight upper
bounds via a novel concept of stochastic global sequential covering. We show
that for a hypothesis class of VC-dimension $\mathsf{VC}$ and $i.i.d.$
generated features of length $T$, the cardinality of the stochastic global
sequential covering can be upper bounded with high probability (whp) by
$e^{O(\mathsf{VC} \cdot \log^2 T)}$. We then improve this bound by introducing
a new complexity measure called the Star-Littlestone dimension, and show that
classes with Star-Littlestone dimension $\mathsf{SL}$ admit a stochastic global
sequential covering of order $e^{O(\mathsf{SL} \cdot \log T)}$. We further
establish upper bounds for real valued classes with finite fat-shattering
numbers. Finally, by applying information-theoretic tools of the fixed design
minimax regrets, we provide lower bounds for the expected worst case minimax
regret. We demonstrate the effectiveness of our approach by establishing tight
bounds on the expected worst case minimax regrets for logarithmic loss and
general mixable losses.
- Abstract（参考訳）: 一般損失関数の下で確率的に生成した特徴を用いた逐次予測とオンラインミニマックス後悔の問題について検討した。
我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。
そのようなミニマックスの後悔に対して、我々は確率的大域的シーケンシャル被覆という新しい概念を通じて厳密な上界を確立する。
VC次元の仮説クラス $\mathsf{VC}$ と $i.i.d.$ の生成した長さ $T$ に対して、確率的大域的シーケンシャル被覆の濃度は $e^{O(\mathsf{VC} \cdot \log^2T)}$ によって高い確率 (whp) で上界できることを示す。
次に、スター・リトルストーン次元と呼ばれる新しい複雑性測度を導入し、スター・リトルストーン次元が$\mathsf{SL}$のクラスが位数$e^{O(\mathsf{SL} \cdot \log T)}$の確率的大域的シーケンシャル被覆を認めることを示す。
さらに,有限ファットシャッタリング数を持つ実数値クラスの上界をさらに確立する。
最後に、固定設計のミニマックス後悔の情報理論ツールを適用することで、期待される最悪のミニマックス後悔に対して低い限界を与える。
対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
関連論文リスト
- Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。
一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
論文 参考訳（メタデータ） (2024-06-10T23:23:52Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。
AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2023-10-04T17:11:15Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。
Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:59:30Z) - Online Learning in Dynamically Changing Environments [11.731001328350983]
一般的な未知の非定常過程からサンプルを引き出す際に,オンライン学習とオンライン後悔の問題を考察する。
我々は、任意の有限VC-次元クラスに対する予想される最悪のケースに対する厳密な($sqrtlog T$ factorまで)有界な$O(sqrtKTcdotmathsfVC(mathcalH)log T)$を証明する。
我々はこれらの結果を、未知の基準測度を持つ一般的なスムーズな逆過程に拡張する。
論文 参考訳（メタデータ） (2023-01-31T21:10:03Z) - Generalized Bandit Regret Minimizer Framework in Imperfect Information
Extensive-Form Game [9.933208900617174]
我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。
NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。
モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
論文 参考訳（メタデータ） (2022-03-11T13:45:42Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach [57.570201404222935]
我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
論文 参考訳（メタデータ） (2021-12-07T00:29:57Z) - Tight Bounds on Minimax Regret under Logarithmic Loss via
Self-Concordance [37.0414602993676]
連続)計量エントロピー $mathcalO(gamma-p)$ at scale $gamma$ を持つ任意の専門家クラスに対して、ミニマックス後悔は $mathcalO(np/(p+1))$ であることを示す。
我々の手法の応用として、専門家の非パラメトリックリプシッツ類に対するミニマックス後悔を解消する。
論文 参考訳（メタデータ） (2020-07-02T14:47:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。