論文の概要: Discounted Thompson Sampling for Non-Stationary Bandit Problems
- arxiv url: http://arxiv.org/abs/2305.10718v2
- Date: Mon, 22 May 2023 07:36:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-23 11:21:41.627128
- Title: Discounted Thompson Sampling for Non-Stationary Bandit Problems
- Title（参考訳）: 非定常バンディット問題に対する安価トンプソンサンプリング
- Authors: Han Qi, Yue Wang, Li Zhu
- Abstract要約: NS-MAB(Non-stationary multi-armed bandit)問題も最近注目されている。
非定常条件の両方に対処するため,ガウシアン先行値を用いたディスカウントトンプソンサンプリング(DS-TS)を提案する。
我々のアルゴリズムは、トンプソンサンプリングに割引係数を組み込むことにより、変化に順応的に適応する。
- 参考スコア（独自算出の注目度）: 13.656518163592349
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Non-stationary multi-armed bandit (NS-MAB) problems have recently received
significant attention. NS-MAB are typically modelled in two scenarios: abruptly
changing, where reward distributions remain constant for a certain period and
change at unknown time steps, and smoothly changing, where reward distributions
evolve smoothly based on unknown dynamics. In this paper, we propose Discounted
Thompson Sampling (DS-TS) with Gaussian priors to address both non-stationary
settings. Our algorithm passively adapts to changes by incorporating a
discounted factor into Thompson Sampling. DS-TS method has been experimentally
validated, but analysis of the regret upper bound is currently lacking. Under
mild assumptions, we show that DS-TS with Gaussian priors can achieve nearly
optimal regret bound on the order of $\tilde{O}(\sqrt{TB_T})$ for abruptly
changing and $\tilde{O}(T^{\beta})$ for smoothly changing, where $T$ is the
number of time steps, $B_T$ is the number of breakpoints, $\beta$ is associated
with the smoothly changing environment and $\tilde{O}$ hides the parameters
independent of $T$ as well as logarithmic terms. Furthermore, empirical
comparisons between DS-TS and other non-stationary bandit algorithms
demonstrate its competitive performance. Specifically, when prior knowledge of
the maximum expected reward is available, DS-TS has the potential to outperform
state-of-the-art algorithms.
- Abstract（参考訳）: NS-MAB(Non-stationary multi-armed bandit)問題も最近注目されている。
NS-MABは通常、ある期間の報酬分布が一定であり、未知の時間ステップで変化し、滑らかに変化し、未知のダイナミクスに基づいて報酬分布がスムーズに進化する、という2つのシナリオでモデル化される。
本稿では,非定常条件の両方に対処するため,ガウシアン前駆体を用いたディスカウントトンプソンサンプリング(DS-TS)を提案する。
このアルゴリズムは、トンプソンサンプリングにディスカウント係数を組み込むことで、変化に受動的に適応する。
DS-TS法は実験的に検証されているが,現在,遺残上界の解析は不十分である。
穏やかな仮定では、ガウス先行のDS-TSは、突然変化する$\tilde{O}(\sqrt{TB_T})$と滑らかに変化する$\tilde{O}(T^{\beta})$の順序でほぼ最適な後悔を達成できることを示し、そこでは、$T$は時間ステップの数、$B_T$はブレークポイントの数、$\beta$は滑らかに変化する環境と関連付けられ、$\tilde{O}$は、$T$と対数的な用語から独立にパラメータを隠している。
さらに、ds-tsと他の非定常バンディットアルゴリズムとの実証的な比較は、その競合性能を示している。
具体的には、最大報酬の事前知識が利用可能であれば、ds-tsは最先端のアルゴリズムを上回る可能性がある。
関連論文リスト
- Efficient and Adaptive Posterior Sampling Algorithms for Bandits [5.050520326139362]
我々は,有界報酬を持つ帯域幅に対するトンプソンサンプリングに基づくアルゴリズムについて検討する。
本稿では2つのパラメータ化トンプソンサンプリングに基づくアルゴリズムを提案する。
両方のアルゴリズムが$O left(Klnalpha+1(T)/Delta right)$ regret bound, ここで$K$はアームの数、$T$は有限学習地平線、$Delta$はサブ最適アームを引っ張る際のラウンドパフォーマンス損失を表す。
論文 参考訳（メタデータ） (2024-05-02T05:24:28Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Langevin Thompson Sampling with Logarithmic Communication: Bandits and
Reinforcement Learning [34.4255062106615]
トンプソンサンプリング(TS)は、使用が容易で、経験的性能に訴えるため、シーケンシャルな意思決定に広く用いられている。
バッチ化された$textitLangevin Thompson Sampling$アルゴリズムを提案する。
アルゴリズムは計算効率が高く,MABでは$mathcalO(log T)$,RLでは$mathcalO(sqrtT)$と同じオーダー最適後悔保証を維持している。
論文 参考訳（メタデータ） (2023-06-15T01:16:29Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Double Thompson Sampling in Finite stochastic Games [10.559241770674724]
有限割引マルコフ決定プロセスの下での探索と利用のトレードオフ問題を考察する。
このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。
論文 参考訳（メタデータ） (2022-02-21T06:11:51Z) - Stochastic Shortest Path: Minimax, Parameter-Free and Towards
Horizon-Free Regret [144.6358229217845]
エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。
我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。
私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
論文 参考訳（メタデータ） (2021-04-22T17:20:48Z) - Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
最短経路 (SSP) は計画と制御においてよく知られた問題である。
また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
論文 参考訳（メタデータ） (2020-06-20T12:10:35Z) - An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic
Gradient Descent and Thompson Sampling [83.48992319018147]
プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。
この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。
本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。
過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
論文 参考訳（メタデータ） (2020-06-07T01:12:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。