論文の概要: On Frequentist Regret of Linear Thompson Sampling
- arxiv url: http://arxiv.org/abs/2006.06790v3
- Date: Thu, 20 Apr 2023 21:35:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-24 19:23:34.346710
- Title: On Frequentist Regret of Linear Thompson Sampling
- Title(参考訳): リニアトンプソンサンプリングの周波数規則について
- Authors: Nima Hamidi, Mohsen Bayati
- Abstract要約: 本稿では,決定者側が $mathbbRd$ の時間依存ベクトル集合から行動を選択し,雑音の報奨を受ける線形帯域問題について検討する。
目的は、後悔を最小限に抑えることであり、決定者の累積的な報奨と、各アクションの期待報奨にアクセスできる神託の報奨とを、一連のT$決定に比較して区別することである。
- 参考スコア(独自算出の注目度): 8.071506311915398
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the stochastic linear bandit problem, where a
decision-maker chooses actions from possibly time-dependent sets of vectors in
$\mathbb{R}^d$ and receives noisy rewards. The objective is to minimize regret,
the difference between the cumulative expected reward of the decision-maker and
that of an oracle with access to the expected reward of each action, over a
sequence of $T$ decisions. Linear Thompson Sampling (LinTS) is a popular
Bayesian heuristic, supported by theoretical analysis that shows its Bayesian
regret is bounded by $\widetilde{\mathcal{O}}(d\sqrt{T})$, matching minimax
lower bounds. However, previous studies demonstrate that the frequentist regret
bound for LinTS is $\widetilde{\mathcal{O}}(d\sqrt{dT})$, which requires
posterior variance inflation and is by a factor of $\sqrt{d}$ worse than the
best optimism-based algorithms. We prove that this inflation is fundamental and
that the frequentist bound of $\widetilde{\mathcal{O}}(d\sqrt{dT})$ is the best
possible, by demonstrating a randomization bias phenomenon in LinTS that can
cause linear regret without inflation.We propose a data-driven version of LinTS
that adjusts posterior inflation using observed data, which can achieve minimax
optimal frequentist regret, under additional conditions. Our analysis provides
new insights into LinTS and settles an open problem in the field.
- Abstract(参考訳): 本稿では, 確率線形バンディット問題について検討し, 意思決定者が "\mathbb{r}^d$" において, 時間依存ベクトル集合から行動を選択し, うるさい報酬を受ける。
その目的は後悔を最小限に抑えることであり、意思決定者の累積的な期待報酬と、t$の一連の決定よりも、各アクションの期待報酬にアクセス可能なオラクルとの差である。
線形トンプソンサンプリング(LinTS)はベイズ的ヒューリスティックであり、そのベイズ的後悔を$\widetilde{\mathcal{O}}(d\sqrt{T})$で表す理論解析によって支持される。
しかし、以前の研究では、LinTSの頻繁な後悔は、後続の分散インフレーションを必要とする$\widetilde{\mathcal{O}}(d\sqrt{dT})$であり、最良の楽観主義に基づくアルゴリズムよりも$\sqrt{d}$より悪いことが示されている。
我々は,このインフレーションが基本であり,インフレーションを伴わずに線形な後悔を生じさせるようなテントのランダム化バイアス現象を実演することにより,その最大値が$\widetilde{\mathcal{o}}(d\sqrt{dt})$となることを証明し,観測データを用いて後方インフレーションを調整するデータ駆動型モデルを提案する。
我々の分析はLinTSに対する新たな洞察を与え、この分野におけるオープンな問題を解決します。
関連論文リスト
- 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) - Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳(メタデータ) (2024-11-12T11:30:53Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
論文 参考訳(メタデータ) (2023-10-02T19:59:39Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳(メタデータ) (2023-07-25T15:42:11Z) - The Sample Complexity of Approximate Rejection Sampling with
Applications to Smoothed Online Learning [29.44582058149344]
n$ の関数としての最適総変分距離が $tildeTheta(fracDf'(n))$ によって与えられることを示す。
次に、スムーズなオンライン学習という非常に異なる分野のアプリケーションを検討します。
論文 参考訳(メタデータ) (2023-02-09T14:20:14Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - Improved Regret Analysis for Variance-Adaptive Linear Bandits and
Horizon-Free Linear Mixture MDPs [12.450760567361531]
オンライン学習問題では,低分散の活用がパフォーマンス保証の厳密化に重要な役割を果たしている。
本研究は, 後悔の限界を著しく改善する新たな分析法を提案する。
我々の分析は、新しい楕円型ポテンシャル数補題に依存している。
論文 参考訳(メタデータ) (2021-11-05T06:47:27Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳(メタデータ) (2021-01-31T16:17:56Z) - Thompson Sampling for Linearly Constrained Bandits [18.477962150017095]
我々はLinConTSについて述べる。LinConTSは、各ラウンドで報酬を得る確率に線形制約を課すバンディットのアルゴリズムである。
また,LinConTSでは,過度な制約違反と累積的制約違反はO(log T)で上限づけられていることを示す。
論文 参考訳(メタデータ) (2020-04-20T13:06:35Z) - Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
有限水平強化学習(RL)における探索・探索ジレンマの検討
本稿では,ランダム化最小二乗値 (RLSVI) の楽観的な変種を紹介する。
マルコフ決定過程が低ランク遷移ダイナミクスを持つという仮定の下で、RSVIの頻繁な後悔は、$widetilde O(d2 H2 sqrtT)$$ d $ が特徴次元であり、$ H $ が地平線であり、$ T $ が総数であることを示す。
論文 参考訳(メタデータ) (2019-11-01T19:48:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。