論文の概要: Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret

• arxiv url: http://arxiv.org/abs/2604.20172v1
• Date: Wed, 22 Apr 2026 04:27:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-23 15:36:10.96418
• Title: Cover meets Robbins while Betting on Bounded Data: $\ln n$ Regret and Almost Sure $\ln\ln n$ Regret
• Title（参考訳）: Coverがバウンドデータに賭けながらRobinsと出会う:$\lnn$ Regretとほぼ確実に$\ln\lnn$ Regret
• Authors: Shubhada Agrawal, Aaditya Ramdas,
• Abstract要約: 本稿では,RobinsとCoverの知見を組み合わせた新たな混合ベッティング戦略を提案する。 われわれの論文は、2つの非常に異なる戦略でデータへの最高の適応性を実現することの価値を最初に指摘したものと思われる。
• 参考スコア（独自算出の注目度）: 39.04174642330437
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider betting against a sequence of data in $[0,1]$, where one is allowed to make any bet that is fair if the data have a conditional mean $m_0 \in (0,1)$. Cover's universal portfolio algorithm delivers a worst-case regret of $O(\ln n)$ compared to the best constant bet in hindsight, and this bound is unimprovable against adversarially generated data. In this work, we present a novel mixture betting strategy that combines insights from Robbins and Cover, and exhibits a different behavior: it eventually produces a regret of $O(\ln \ln n)$ on \emph{almost} all paths (a measure-one set of paths if each conditional mean equals $m_0$ and intrinsic variance increases to $\infty$), but has an $O(\log n)$ regret on the complement (a measure zero set of paths). Our paper appears to be the first to point out the value in hedging two very different strategies to achieve a best-of-both-worlds adaptivity to stochastic data and protection against adversarial data. We contrast our results to those in~\cite{agrawal2025regret} for a sub-Gaussian mixture on unbounded data: their worst-case regret has to be unbounded, but a similar hedging delivers both an optimal betting growth-rate and an almost sure $\ln\ln n$ regret on stochastic data. Finally, our strategy witnesses a sharp game-theoretic upper law of the iterated logarithm, analogous to~\cite{shafer2005probability}.
• Abstract（参考訳）: もしデータが条件平均$m_0 \in (0,1)$を持つなら、公正な賭けをすることができる。 Coverのユニバーサルポートフォリオアルゴリズムは、後見の最良の定数ベットと比較すると、$O(\ln n)$の最悪の後悔をもたらす。 最終的に、$O(\ln \ln n)$ on \emph{almost} all paths(各条件平均が$m_0$と内在的分散が$\infty$に増加する場合の経路の測度対1の集合)の後悔を生じさせるが、補集合(経路の測度ゼロの集合)に対して$O(\log n)$ regretを持つ。 我々の論文は、確率的データに対するベスト・オブ・ワールド・アダプティビティを実現し、敵対的データに対する保護を実現するために、2つの非常に異なる戦略をヘッジする価値を最初に指摘したものと思われる。 この結果と, 非有界データ上のガウス系混合物の〜\cite{agrawal2025regret}では, 最悪ケースの後悔は非有界データでなければならないが, 同様のヘッジは, 最適なベッティング成長速度とほぼ確実な$\ln\lnn$後悔の両方をもたらす。 最終的に、我々の戦略は、反復対数の鋭いゲーム理論上の法則を、~\cite{shafer 2005probability}に類似している。

関連論文リスト

• Eventually LIL Regret: Almost Sure $\ln\ln T$ Regret for a sub-Gaussian Mixture on Unbounded Data [39.04174642330437]
  古典的なガウス混合がパスワイズ(決定論的)な後悔境界を満たすことを証明する。 この研究は、敵対的なオンライン学習の世界を橋渡しするのにどのように役立つかを説明します。
  論文  参考訳（メタデータ） (2025-12-13T13:34:03Z)
• 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)
• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。 本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-01T09:41:45Z)
• Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
  我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。 逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。 我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
  論文  参考訳（メタデータ） (2023-11-02T03:41:58Z)
• 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)

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

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