論文の概要: Efficient Simple Regret Algorithms for Stochastic Contextual Bandits

• arxiv url: http://arxiv.org/abs/2601.21167v1
• Date: Thu, 29 Jan 2026 02:09:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.511695
• Title: Efficient Simple Regret Algorithms for Stochastic Contextual Bandits
• Title（参考訳）: 確率的文脈帯域に対する効率的な簡易回帰アルゴリズム
• Authors: Shuai Liu, Alireza Bakhtiari, Alex Ayoub, Botao Hao, Csaba Szepesvári,
• Abstract要約: 簡単な後悔の目的の下で,文脈的ロジスティックな包帯について検討する。 本稿では, 簡単な後悔を解くアルゴリズムを初めて提案する。 我々はまた、単純回帰設定に合わせた新しいトンプソンサンプリングの変種も導入する。
• 参考スコア（独自算出の注目度）: 32.5817931126341
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study stochastic contextual logistic bandits under the simple regret objective. While simple regret guarantees have been established for the linear case, no such results were previously known for the logistic setting. Building on ideas from contextual linear bandits and self-concordant analysis, we propose the first algorithm that achieves simple regret $\tilde{\mathcal{O}}(d/\sqrt{T})$. Notably, the leading term of our regret bound is free of the constant $κ= \mathcal O(\exp(S))$, where $S$ is a bound on the magnitude of the unknown parameter vector. The algorithm is shown to be fully tractable when the action set is finite. We also introduce a new variant of Thompson Sampling tailored to the simple-regret setting. This yields the first simple regret guarantee for randomized algorithms in stochastic contextual linear bandits, with regret $\tilde{\mathcal{O}}(d^{3/2}/\sqrt{T})$. Extending this method to the logistic case, we obtain a similarly structured Thompson Sampling algorithm that achieves the same regret bound -- $\tilde{\mathcal{O}}(d^{3/2}/\sqrt{T})$ -- again with no dependence on $κ$ in the leading term. The randomized algorithms, as expected, are cheaper to run than their deterministic counterparts. Finally, we conducted a series of experiments to empirically validate these theoretical guarantees.
• Abstract（参考訳）: 簡単な後悔目的の下で,確率的文脈ロジスティックな包帯について検討した。 線形の場合、単純な後悔の保証が確立されているが、以前はロジスティックな設定ではそのような結果は知られていなかった。 文脈線形包帯と自己調和解析のアイデアに基づいて、簡単な後悔を$\tilde{\mathcal{O}}(d/\sqrt{T})$とするアルゴリズムを提案する。 特に、後悔境界の先頭項は定数 $κ= \mathcal O(\exp(S))$ を含まない。 このアルゴリズムは、作用集合が有限であるときに完全に求心可能であることが示される。 我々はまた、単純回帰設定に合わせた新しいトンプソンサンプリングの変種も導入する。 これにより、確率的文脈線形包帯におけるランダム化アルゴリズムに対する最初の単純な後悔の保証が、後悔の$\tilde{\mathcal{O}}(d^{3/2}/\sqrt{T})$である。 この手法をロジスティックケースに拡張すると、同様に構造化されたトンプソンサンプリングアルゴリズムが、同じ後悔境界 --$\tilde{\mathcal{O}}(d^{3/2}/\sqrt{T})$ -- を達成する。 ランダム化されたアルゴリズムは、予想通り、決定論的アルゴリズムよりも実行しやすい。 最後に、これらの理論的保証を実証的に検証する一連の実験を行った。

関連論文リスト

• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits [18.971564419292893]
  我々は、$O(sqrtdTlog T)$ regret boundで、$d$は文脈の次元、$T$は時間地平線であるような線形文脈的帯域幅アルゴリズムを提案する。 提案アルゴリズムは,探索を明示的ランダム化により埋め込んだ新しい推定器を備える。
  論文  参考訳（メタデータ） (2022-06-11T02:43:17Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Non-stationary Linear Bandits Revisited [26.082923174615495]
  非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。 これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
  論文  参考訳（メタデータ） (2021-03-09T10:07:17Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Low-Rank Generalized Linear Bandit Problems [19.052901817304743]
  低ランク線型バンドイット問題において、作用の報酬は、作用と未知の低ランク行列$Theta*$の間の内部積である。 低ランク行列の被覆によって構築される指数重み付き平均予測器と、オンラインから信頼度セットへの変換パバシ2012onlineの新たな組み合わせに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T15:30:14Z)

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

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