論文の概要: Randomized Exploration for Linear Bandits via Absolute Perturbations

• arxiv url: http://arxiv.org/abs/2606.28616v1
• Date: Fri, 26 Jun 2026 21:22:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-30 18:07:15.620227
• Title: Randomized Exploration for Linear Bandits via Absolute Perturbations
• Title（参考訳）: 絶対摂動による線形帯域のランダム化探索
• Abstract要約: 絶対トンプソンサンプリング(Absolute Thompson Sampling、ATS)は、トンプソンサンプリング(TS)の単純な修正であり、期待する際の楽観性を保証する。 ATS は $tildeO(d3/2sqrtK)$ regret を達成する。 Ensemble Absolute Thompson Sampling (EATS) は、アンサンブルサイズによる正規化を伴う複数の絶対摂動の最大値を取る。
• 参考スコア（独自算出の注目度）: 29.1817020301259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves $\tilde{O}(d^{3/2}\sqrt{K})$ regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.
• Abstract（参考訳）: 確率線形帯域において、正準上信頼境界 (UCB) アルゴリズムは単純な頻繁な後悔分析を許容するが、トンプソンサンプリング (TS) は計算的に魅力的であるが、非最適性のために解析するのが通常困難である。 本稿では,符号付き探索ノイズを絶対値に置き換えることにより,期待値の楽観性を確実にするTSの簡易な修正であるAbsolute Thompson Sampling (ATS)を提案する。 これはTSの計算効率を保ちながら、TS分析に共通する技術的な反集中論を回避し、単純な UCB スタイルの後悔分析を可能にする。 ATS は TS の線形包帯における既存の境界値に一致して $\tilde{O}(d^{3/2}\sqrt{K})$ regret を達成することを示す。 さらに、アンサンブルサイズによる正規化を伴う複数の絶対摂動の最大値を取るアンサンブル絶対トンプソンサンプリング(EATS)を導入する。 アンサンブルのサイズが大きくなるにつれて、EATS は UCB の目的に収束し、限界における UCB の挙動を回復する。 実験により、中程度のアンサンブルサイズは、既に高いパフォーマンスをもたらすことが示されている。 我々の結果は、ランダムな探索と決定論的楽観主義の橋渡しを理論と実践の両方で示している。

関連論文リスト

• Tight Generalization Bounds for Noiseless Inverse Optimization [20.72173263660803]
  逆最適化(IO)は、観測されたコンテキスト-アクションデータから意思決定者の目的のパラメータを推測する。 誘導されたアクションセットに対して高確率の$O(fracdT)$boundを提供し、$d$は未知のパラメータの数で、$T$はトレーニングデータセットのサイズです。 我々は、$O(fracdT)$レートが、ここで考慮されたすべての一貫した推定値に対して厳密であることを示し、その結果を、即時および累積的後悔の両方に拡張する。
  論文  参考訳（メタデータ） (2026-05-09T10:33:38Z)
• Thompson Sampling for Multi-Objective Linear Contextual Bandit [29.777578580338584]
  本稿では,複数の競合する対象を同時に最適化しなければならない多目的線形文脈帯域問題について検討する。 本稿では,テキストファーストのトンプソンサンプリングアルゴリズムである textttMOL-TS を提案する。 提案手法の利点を実証し, 後悔の最小化と多目的性能の向上を実証した。
  論文  参考訳（メタデータ） (2025-11-30T15:18:01Z)
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits [54.220839560203096]
  FGTSVA, 変分対応型トンプソンサンプリングアルゴリズムを提案する。 新しいデカップリング係数を$mathrmdc$で表すと、FGTS-VAは$tildeO(sqrtmathrmdccdotlog|mathcalF|$)を後悔する。 文脈線形帯域の設定において、FGTSVAの後悔境界は UCB ベースと一致する
  論文  参考訳（メタデータ） (2025-11-03T23:25:41Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective [17.53150194998013]
  本稿では、トンプソンサンプリング(TS)フレームワークに近似(SA)を組み込んだTS-SAを紹介する。 各ラウンドにおいて、TS-SAは直近の報酬のみを用いて後部近似を構築し、時間とともにノイズの多い提案にSAステップを適用する。 これは、アルゴリズム全体を通して静止後ターゲットを近似するものとして解釈できる。
  論文  参考訳（メタデータ） (2025-10-06T17:01:29Z)
• Thompson Sampling-like Algorithms for Stochastic Rising Bandits [20.143361197609934]
  レイジング・レステッド・バンディット(Rising rested bandit、SRRB)は、腕が引っ張られるにつれて、期待される報酬が増加する舞台である。 この研究は、SRRBにおけるそのようなアルゴリズムに対する新たな後悔の分析を提供し、課題を強調し、独立した技術ツールを提供する。
  論文  参考訳（メタデータ） (2025-05-17T17:19:07Z)
• Scalable Exploration via Ensemble++ [29.871658730354437]
  ランダムな線形結合を持つ新しい共有要素アンサンブルアーキテクチャを用いたスケーラブルな探索フレームワークを提案する。 線形帯域については、Ensemble++がThompson Samplingに匹敵する後悔を達成していることを示す理論的保証を提供する。 我々は、固定された特徴を学習可能なニューラル表現に置き換えることで、この理論の基礎を非線形報酬に拡張する。
  論文  参考訳（メタデータ） (2024-07-18T06:16:09Z)
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
  本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。 最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
  論文  参考訳（メタデータ） (2022-06-07T18:08:21Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討 我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。 この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
  論文  参考訳（メタデータ） (2020-06-11T17:12:11Z)
• Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
  我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。 また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
  論文  参考訳（メタデータ） (2020-04-20T13:06:35Z)

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

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