Fugu-MT 論文翻訳(概要): On Worst-case Regret of Linear Thompson Sampling

論文の概要: On Worst-case Regret of Linear Thompson Sampling

arxiv url: http://arxiv.org/abs/2006.06790v2
Date: Fri, 6 Nov 2020 19:05:55 GMT
ステータス: 処理完了
システム内更新日: 2022-11-22 12:38:58.171005
Title: On Worst-case Regret of Linear Thompson Sampling
Title（参考訳）: リニアトンプソンサンプリングの最悪の再帰について
Authors: Nima Hamidi, Mohsen Bayati
Abstract要約: 線形バンディット問題に対する線形トンプソンサンプリング(LinTS)の最悪の後悔について考察する。 LinTSで唯一知られている最悪の後悔は、citeagrawal2013thompson,abeille 2017によるものであり、$widetildemathcalO(dsqrtdT)$である。
参考スコア（独自算出の注目度）: 8.071506311915398
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we consider the worst-case regret of Linear Thompson Sampling (LinTS) for the linear bandit problem. \citet{russo2014learning} show that the Bayesian regret of LinTS is bounded above by $\widetilde{\mathcal{O}}(d\sqrt{T})$ where $T$ is the time horizon and $d$ is the number of parameters. While this bound matches the minimax lower-bounds for this problem up to logarithmic factors, the existence of a similar worst-case regret bound is still unknown. The only known worst-case regret bound for LinTS, due to \cite{agrawal2013thompson,abeille2017linear}, is $\widetilde{\mathcal{O}}(d\sqrt{dT})$ which requires the posterior variance to be inflated by a factor of $\widetilde{\mathcal{O}}(\sqrt{d})$. While this bound is far from the minimax optimal rate by a factor of $\sqrt{d}$, in this paper we show that it is the best possible one can get, settling an open problem stated in \cite{russo2018tutorial}. Specifically, we construct examples to show that, without the inflation, LinTS can incur linear regret up to time $\exp(\Omega(d))$. We then demonstrate that, under mild conditions, a slightly modified version of LinTS requires only an $\widetilde{\mathcal{O}}(1)$ inflation where the constant depends on the diversity of the optimal arm.
Abstract（参考訳）: 本稿では,線形帯域問題に対する線形トンプソンサンプリング(LinTS)の最悪の後悔について考察する。 \citet{russo2014learning} は、LinTS のベイズ的後悔は、$\widetilde{\mathcal{O}}(d\sqrt{T})$ で、$T$ は時間的地平線であり、$d$ はパラメータの数であることを示している。この境界は、対数的要因までこの問題のミニマックス下限と一致するが、同様の最悪の後悔境界の存在はいまだ不明である。責任を負う唯一の最悪の後悔は、\cite{agrawal2013thompson,abeille2017linear} が$\widetilde{\mathcal{o}}(d\sqrt{dt})$ であり、後方の分散を$\widetilde{\mathcal{o}}(\sqrt{d})$ で膨らませる必要がある。このバウンドは、$\sqrt{d}$という係数でminimaxの最適レートに遠く及ばないが、本論文では、それが取得可能な最良であることを示し、 \cite{russo2018tutorial} で述べられているオープン問題を解く。具体的には、インフレーションがなければ、LinTS は時間$\exp(\Omega(d))$まで線形後悔を引き起こすことができることを示す。次に、穏やかな条件下では、LinTSのわずかに修正されたバージョンは、最適なアームの多様性に依存するような$\widetilde{\mathcal{O}}(1)$インフレーションしか必要としないことを示した。

関連論文リスト

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)

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

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