論文の概要: Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits

• arxiv url: http://arxiv.org/abs/2610.36245v1
• Date: Mon, 26 Oct 2026 20:23:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-29 04:15:49.197247
• Title: Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits
• Title（参考訳）: 対数価格の3つの世界:ベースラインプロテクションされたBest-of-Both-Worlds Combinatorial Semi-Bandits
• Abstract要約: 任意の有限作用集合を持つ半帯域に対する水平自由混合スキームを提案する。 混合相ではエントロピー-FTRL、純相ではハイブリッド-FTRLを用いる。 したがって、ベースライン保護、対向ロバスト性、適応性は、1つのスキームと2つのベースラーナーから得られる。
• 参考スコア（独自算出の注目度）: 2.619625212743132
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Improving on a baseline requires exploring away from it, precisely where its performance may be lost. We propose DUET (Doubling Under Empirical Tests), a horizon-free phased mixing scheme for combinatorial semi-bandits with arbitrary finite action sets. Two observable tests decide when to double the learning weight and when to double the empirical-regret budget and restart. We instantiate the scheme with entropy-FTRL in mixed phases and hybrid-FTRL in pure phases. Assuming the baseline selects every arm with positive probability, this instantiation keeps expected baseline regret logarithmic in $T$, while its expected regret to every fixed action is $\widetilde{O}(\sqrt{T})$ under non-anticipating adversarial losses and polylogarithmic, gap-dependent, under i.i.d. losses with a unique optimal action. All three guarantees hold at every deterministic horizon, and the algorithm knows neither the horizon, nor the gap, nor the environment type. Baseline protection, adversarial robustness, and stochastic adaptivity thus come from one scheme and two base learners, at the price of a logarithm.
• Abstract（参考訳）: ベースラインの改善には、そのパフォーマンスが失われる可能性がある場所を正確に調査する必要がある。 任意の有限作用集合を持つ組合せ半帯域に対する水平自由位相混合スキームであるDUET(Doubling Under Empirical Tests)を提案する。 観測可能な2つのテストは、学習重量を2倍にし、経験的な予算を2倍にし、再起動するタイミングを決定する。 混合相ではエントロピー-FTRL、純相ではハイブリッド-FTRLを用いる。 ベースラインが正の確率で全てのアームを選択すると、このインスタンス化は期待されるベースライン後悔対数を$T$で維持するが、全ての固定アクションに対する期待された後悔は$\widetilde{O}(\sqrt{T})$である。 3つの保証はすべての決定論的地平線で保持され、アルゴリズムは地平線もギャップも環境タイプも知らない。 ベースライン保護、対数ロバスト性、確率的適応性は、対数の価格で、1つのスキームと2つのベースラーナーから得られる。

関連論文リスト

• Rate-Optimal Algorithm for Adversarial Linear CMDPs [8.015940996821541]
  逆線形制約マルコフ決定過程(CMDP)を未知の遷移で検討する。 本稿では,Slater の条件を仮定することなく,$widetildemathcalO(sqrtK)$ regret と cumulative 制約違反を実現する,新しい原始双対アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-10-01T02:03:07Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Representation Without Reward: A JEPA Audit for LLM Fine-Tuning [1.2691047660244335]
  JEPA(Joint-embedding predictive Architectures)は、モデルが観測された出力よりも遅延表現を予測できるように訓練された時に、より有用な抽象化を学ぶべきであることを提案している。 自己回帰型言語モデルの微調整には、この原理はより厳密な要件を必要とする。 我々は、Llama-3.2-1B-Instruct LoRA を用いて、自然言語からレジェックス生成におけるその要件を検証した。
  論文  参考訳（メタデータ） (2026-05-14T20:27:32Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。 我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
  論文  参考訳（メタデータ） (2023-05-26T23:20:48Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。 我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。 我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
  論文  参考訳（メタデータ） (2023-03-17T17:53:28Z)
• Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds [27.92755687977196]
  本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。 高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。 提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
  論文  参考訳（メタデータ） (2023-02-24T00:02:24Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)

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

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