論文の概要: An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits

• arxiv url: http://arxiv.org/abs/2412.02861v2
• Date: Thu, 20 Feb 2025 18:24:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-21 14:25:56.320594
• Title: An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits
• Title（参考訳）: ロジスティックバンドのためのトンプソンサンプリングの情報理論解析
• Authors: Amaury Gouverneur, Borja Rodríguez-Gálvez, Tobias J. Oechtering, Mikael Skoglund,
• Abstract要約: 本稿では,ロジスティックバンディット問題に対するトンプソンサンプリングアルゴリズムの性能について検討する。 我々は、$O(d/alphaqrtT log(beta T/d))$ of regret incurred after $T$ expected of Smpling steps.
• 参考スコア（独自算出の注目度）: 36.37704574907495
• License:
• Abstract: We study the performance of the Thompson Sampling algorithm for logistic bandit problems. In this setting, an agent receives binary rewards with probabilities determined by a logistic function, $\exp(\beta \langle a, \theta \rangle)/(1+\exp(\beta \langle a, \theta \rangle))$, with slope parameter $\beta>0$, and where both the action $a\in \mathcal{A}$ and parameter $\theta \in \mathcal{O}$ lie within the $d$-dimensional unit ball. Adopting the information-theoretic framework introduced by Russo and Van Roy (2016), we analyze the information ratio, a statistic that quantifies the trade-off between the immediate regret incurred and the information gained about the optimal action. We improve upon previous results by establishing that the information ratio is bounded by $\tfrac{9}{2}d\alpha^{-2}$, where $\alpha$ is a minimax measure of the alignment between the action space $\mathcal{A}$ and the parameter space $\mathcal{O}$, and is independent of $\beta$. Using this result, we derive a bound of order $O(d/\alpha\sqrt{T \log(\beta T/d)})$ on the Bayesian expected regret of Thompson Sampling incurred after $T$ time steps. To our knowledge, this is the first regret bound for logistic bandits that depends only logarithmically on $\beta$ while being independent of the number of actions. In particular, when the action space contains the parameter space, the bound on the expected regret is of order $\tilde{O}(d \sqrt{T})$.
• Abstract（参考訳）: 本稿では,ロジスティックバンディット問題に対するトンプソンサンプリングアルゴリズムの性能について検討する。 この設定では、エージェントは、ロジスティック関数によって決定される確率で二進報酬を受ける。 $\exp(\beta \langle a, \theta \rangle)/(1+\exp(\beta \langle a, \theta \rangle))$, with slope parameter $\beta>0$, and where the action $a\in \mathcal{A}$ and parameters $\theta \in \mathcal{O}$は、$d$次元単位球内にある。 Russo と Van Roy (2016) が導入した情報理論の枠組みを応用し、情報比率、即時後悔と最適な行動に関する情報との間のトレードオフを定量化する統計分析を行う。 我々は、情報比が$\tfrac{9}{2}d\alpha^{-2}$で有界であることを確立することにより、以前の結果を改善する。$\alpha$はアクション空間$\mathcal{A}$とパラメータ空間$\mathcal{O}$のアライメントの最小値測度であり、$\beta$とは独立である。 この結果を用いて、ベイジアン予想されるトンプソンサンプリングのT$時間ステップの後に生じた後悔について、位数$O(d/\alpha\sqrt{T \log(\beta T/d)})$を導出する。 私たちの知る限り、これはロジスティックな包帯に対する最初の後悔であり、アクションの数に依存しながら$\beta$に対数的にのみ依存する。 特に、アクション空間がパラメータ空間を含むとき、期待される後悔の束縛は$\tilde{O}(d \sqrt{T})$である。

関連論文リスト

• New Rates in Stochastic Decision-Theoretic Online Learning under Differential Privacy [17.711455925206298]
  HuとMehta(2024年)は、オープンな問題を提起した:$varepsilon$-differential privacyの下で、決定論的オンライン学習($K$アクションと$T$ラウンドを含む)の最適なインスタンス依存率は何ですか? 本稿では,2つの新しい結果を得ることで,この問題に部分的に対処する。まず,$Oleft(fraclog KDelta_min + fraclog2Kvarepsilonright)$。 第二に
  論文  参考訳（メタデータ） (2025-02-16T05:13:51Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators [23.313461266708877]
  置換行列 $bPitrue$ とスパース信号 $bbetatrue$ をシャッフルラベルから再構成する。 提案した推定器は, 穏やかな条件下で, 基本トラス$(bPitrue, supp(bbetatrue))$が得られることを示す。
  論文  参考訳（メタデータ） (2023-03-20T16:14:58Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
  タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。 このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。 情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
  論文  参考訳（メタデータ） (2021-08-11T20:42:46Z)
• Cascading Bandit under Differential Privacy [21.936577816668944]
  本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。 DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。 Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
  論文  参考訳（メタデータ） (2021-05-24T07:19:01Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)

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

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