論文の概要: An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits
- arxiv url: http://arxiv.org/abs/2412.02861v1
- Date: Tue, 03 Dec 2024 21:55:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-05 15:09:52.015494
- 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要約: 本稿では,ロジスティックバンディット問題に対するトンプソンサンプリングアルゴリズムの性能について検討する。
最適報酬と実報酬の2乗差の比として定義される情報比を解析する。
我々は$O(dsqrtT log(beta T/d))$の後悔のバウンダリを得る。
- 参考スコア(独自算出の注目度): 36.37704574907495
- License:
- Abstract: We study the performance of the Thompson Sampling algorithm for logistic bandit problems, where the agent receives binary rewards with probabilities determined by a logistic function $\exp(\beta \langle a, \theta \rangle)/(1+\exp(\beta \langle a, \theta \rangle))$. We focus on the setting where the action $a$ and parameter $\theta$ lie within the $d$-dimensional unit ball with the action space encompassing the parameter space. Adopting the information-theoretic framework introduced by (Russo $\&$ Van Roy, 2015), we analyze the information ratio, which is defined as the ratio of the expected squared difference between the optimal and actual rewards to the mutual information between the optimal action and the reward. Improving upon previous results, we establish that the information ratio is bounded by $\tfrac{9}{2}d$. Notably, we obtain a regret bound in $O(d\sqrt{T \log(\beta T/d)})$ that depends only logarithmically on the parameter $\beta$.
- Abstract(参考訳): エージェントはロジスティック関数 $\exp(\beta \langle a, \theta \rangle)/(1+\exp(\beta \langle a, \theta \rangle)$ によって決定される確率で二進報酬を受ける。
我々は、アクション$a$とパラメータ$\theta$がパラメータ空間を含むアクション空間を持つ$d$次元のユニットボール内にある設定に焦点を当てる。
最適行動と報奨の相互情報に対する最適報酬と実際の報奨の2乗差の比として定義される情報比を、Russo $\&$ Van Roy, 2015で導入された情報理論フレームワークを用いて分析する。
以前の結果を改善して、情報比が$\tfrac{9}{2}d$で有界であることが確かめられる。
特に、$O(d\sqrt{T \log(\beta T/d)})$において、パラメータ $\beta$ を対数的にのみ依存する後悔境界を得る。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。