論文の概要: Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data

• arxiv url: http://arxiv.org/abs/2512.12325v1
• Date: Sat, 13 Dec 2025 13:34:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-16 17:54:56.21792
• Title: Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data
• Title（参考訳）: 最終的に LIL Regret: ほぼ確実に$\ln\ln T$ Regret for a sub-Gaussian Mixture on unbounded Data
• Authors: Shubhada Agrawal, Aaditya Ramdas,
• Abstract要約: 古典的なガウス混合がパスワイズ(決定論的)な後悔境界を満たすことを証明する。 この研究は、敵対的なオンライン学習の世界を橋渡しするのにどのように役立つかを説明します。
• 参考スコア（独自算出の注目度）: 39.04174642330437
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that a classic sub-Gaussian mixture proposed by Robbins in a stochastic setting actually satisfies a path-wise (deterministic) regret bound. For every path in a natural ``Ville event'' $E_α$, this regret till time $T$ is bounded by $\ln^2(1/α)/V_T + \ln (1/α) + \ln \ln V_T$ up to universal constants, where $V_T$ is a nonnegative, nondecreasing, cumulative variance process. (The bound reduces to $\ln(1/α) + \ln \ln V_T$ if $V_T \geq \ln(1/α)$.) If the data were stochastic, then one can show that $E_α$ has probability at least $1-α$ under a wide class of distributions (eg: sub-Gaussian, symmetric, variance-bounded, etc.). In fact, we show that on the Ville event $E_0$ of probability one, the regret on every path in $E_0$ is eventually bounded by $\ln \ln V_T$ (up to constants). We explain how this work helps bridge the world of adversarial online learning (which usually deals with regret bounds for bounded data), with game-theoretic statistics (which can handle unbounded data, albeit using stochastic assumptions). In short, conditional regret bounds serve as a bridge between stochastic and adversarial betting.
• Abstract（参考訳）: 我々は、ロビンスによって確率的な設定で提案された古典的なガウス混合が、実際にはパスワイズ(決定論的)な後悔境界を満たすことを証明した。 自然の ``Ville event'' の $E_α$ の全ての経路に対して、この後悔は $T$ を $\ln^2(1/α)/V_T + \ln (1/α) + \ln \ln V_T$ で制限する。 (境界は$\ln(1/α) + \ln \ln V_T$ if $V_T \geq \ln(1/α)$に減少する。 ) データが確率的であれば、E_α$が分布の広いクラス(例えば、準ガウス、対称、分散有界など)の下で少なくとも1-α$の確率を持つことを示すことができる。 実際、確率 1 の Ville イベント $E_0$ において、$E_0$ のすべての経路の後悔は最終的に $\ln \ln V_T$ (定数まで) で束縛される。 この研究は、対戦型オンライン学習(通常、有界データに対する後悔的な境界を扱う)の世界と、ゲーム理論統計(確率論的仮定を用いて、非有界データを扱うことができる)との橋渡しにどのように役立つかを説明します。 言い換えれば、条件付き後悔境界は確率的と敵対的賭けの間の橋渡しとして機能する。

関連論文リスト

• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
  論文  参考訳（メタデータ） (2025-03-15T07:09:36Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
  アルゴリズムが「割引なし」の場合、予想される遊びの割引エルゴジック分布が粗相関平衡(CCE)の集合に収束することを示した。 ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
  論文  参考訳（メタデータ） (2021-03-08T05:15:31Z)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。 差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。 同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
  論文  参考訳（メタデータ） (2021-02-16T02:48:16Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。