論文の概要: Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

• arxiv url: http://arxiv.org/abs/2606.09191v1
• Date: Mon, 08 Jun 2026 08:26:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:06.834063
• Title: Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards
• Title（参考訳）: サブガウス・リワードを伴うリスク・アバースバンドに対するトンプソンサンプリングの漸近的最適性
• Authors: Joel Q. L. Chang,
• Abstract要約: $text-mathrmNPTS_mathrmSG$はアンカーフリーの非パラメトリックトンプソンサンプリングアルゴリズムである。 我々は、$text-mathrmNPTS_mathrmSG$が、$log n$の先頭の順にインスタンス依存の下位境界と一致することを証明した。
• 参考スコア（独自算出の注目度）: 1.370633147306388
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that $ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in $\log n$, establishing it as asymptotically optimal for any continuous risk functional $ρ$ (CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of $ρ$: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions. The bounded-support case is developed first as a stepping stone sharing the same proof structure. The key technical contributions are a discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), each projecting the growing-alphabet Dirichlet posterior onto a fixed grid via the Dirichlet aggregation property, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.
• Abstract（参考訳）: リスク-逆バンディットに対するアンカーフリーな非パラメトリックトンプソンサンプリングアルゴリズムである$ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}$は、ガウスの腕を含む有界密度と亜ガウスの尾を持つ分布のクラスにおける任意の連続リスク汎関数 $ρ$(CVaR, 平均分散, シャープ比, 歪みリスク測度など)に対して漸近的に最適であることを示す。 この結果とその有界サポートはともに$ρ$の連続性しか必要としない: 事前パラメトリックトンプソンサンプリング結果の優位条件よりも厳密に弱く、UTB型アルゴリズムのリプシッツ条件よりも厳密に弱く、パラメトリック報酬仮定のないシャープ比のような非リプシッツ函数に対する最初のインスタンス最適保証を与える。 有界支持ケースは、まず、同じ証明構造を共有するステッピング石として開発される。 主要な技術的貢献は、離散化補題(有界支持)と切り離された離散化補題(準ガウスの尾)であり、成長アルファベットのディリクレの後方をディリクレ集約特性を介して固定格子上に投影し、全ての多項式プレファクタを標本サイズに依存しない一定の程度に保持し、先行証明を妨害する超指数障壁を破る。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints [21.38692458445459]
  ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。 単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2023-10-02T08:07:36Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)

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

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