論文の概要: Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits

• arxiv url: http://arxiv.org/abs/2105.14586v1
• Date: Sun, 30 May 2021 17:28:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-01 17:29:38.580609
• Title: Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits
• Title（参考訳）: kolmogorov-smirnov test-based active-adaptive thompson sampling for non-stationary bandits
• Authors: Gourab Ghatak, Hardhik Mohanty, Aniq Ur Rahman
• Abstract要約: 我々は,非定常マルチアーム・バンディット(MAB)フレームワークを考察し,コルモゴロフ・スミルノフ(KS)テストに基づくトンプソンサンプリング(TS-KS)アルゴリズムを提案する。 特に、両腕のバンディットの場合、報奨分布のサンプル数に基づいて境界を導出し、一度変化が生じたときにその変化を検出する。 その結果,TS-KSアルゴリズムは静的TSアルゴリズムよりも優れた性能を示し,非定常環境向けに設計された他の帯域幅アルゴリズムよりも優れた性能を示した。
• 参考スコア（独自算出の注目度）: 2.879036956042183
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the non-stationary multi-armed bandit (MAB) framework and propose a Kolmogorov-Smirnov (KS) test based Thompson Sampling (TS) algorithm named TS-KS, that actively detects change points and resets the TS parameters once a change is detected. In particular, for the two-armed bandit case, we derive bounds on the number of samples of the reward distribution to detect the change once it occurs. Consequently, we show that the proposed algorithm has sub-linear regret. Contrary to existing works, our algorithm is able to detect a change when the underlying reward distribution changes even though the mean reward remains the same. Finally, to test the efficacy of the proposed algorithm, we employ it in two case-studies: i) task-offloading scenario in wireless edge-computing, and ii) portfolio optimization. Our results show that the proposed TS-KS algorithm outperforms not only the static TS algorithm but also it performs better than other bandit algorithms designed for non-stationary environments. Moreover, the performance of TS-KS is at par with the state-of-the-art forecasting algorithms such as Facebook-PROPHET and ARIMA.
• Abstract（参考訳）: 本稿では,mab(non-stationary multi-armed bandit)フレームワークを検討し,ts-ks(kolmogorov-smirnov)テストに基づくts-ks(ts)アルゴリズムを提案する。 特に、両腕のバンディットの場合、報奨分布のサンプル数に基づいて境界を導出し、一度変化が生じたときにその変化を検出する。 その結果,提案アルゴリズムはサブ線形後悔であることがわかった。 既存の研究とは対照的に,平均報酬が同じであっても,基礎となる報酬分布が変化しても,アルゴリズムは変化を検出することができる。 最後に,提案アルゴリズムの有効性を検証するために,無線エッジコンピューティングにおけるタスクオフロードシナリオとポートフォリオ最適化の2つのケーススタディを用いた。 その結果,提案アルゴリズムは静的TSアルゴリズムだけでなく,非定常環境向けに設計された他の帯域幅アルゴリズムよりも優れていた。 さらに、TS-KSの性能は、Facebook-PROPHETやARIMAのような最先端の予測アルゴリズムと同等である。

関連論文リスト

• A Batch Sequential Halving Algorithm without Performance Degradation [0.8283940114367677]
  簡単な逐次バッチアルゴリズムでは,実運用環境での性能が劣化しないことを示す。 実験により,固定サイズバッチ設定におけるアルゴリズムの頑健な性質を実証し,我々の主張を実証的に検証する。
  論文  参考訳（メタデータ） (2024-06-01T12:41:50Z)
• 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)
• VITS : Variational Inference Thompson Sampling for contextual bandits [10.028119153832346]
  我々は、文脈的帯域幅に対するトンプソンサンプリング(TS)アルゴリズムの変種を導入・解析する。 ガウス変分推論に基づく新しいアルゴリズムであるValational Inference Thompson sample VITSを提案する。 我々は,VITS が線形文脈帯域に対して従来の TS の次元とラウンド数で同じ順序のサブ線形後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-19T17:53:22Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。 本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。 我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-03-15T13:17:53Z)
• Algorithms for Adaptive Experiments that Trade-off Statistical Analysis with Reward: Combining Uniform Random Assignment and Reward Maximization [50.725191156128645]
  トンプソンサンプリングのようなマルチアームバンディットアルゴリズムは適応的な実験を行うのに利用できる。 統計的解析のための一様ランダム化の利点を組み合わせた2つのアルゴリズムを探索する2つのアーム実験のシミュレーションを提案する。
  論文  参考訳（メタデータ） (2021-12-15T22:11:58Z)
• Extreme Bandits using Robust Statistics [12.6543086847761]
  我々は,古典的バンディット設定における期待値とは対照的に,極端な値のみが関心を持つ状況に動機づけられたマルチアームバンディット問題を考える。 本研究では,ロバストな統計量を用いた分布自由アルゴリズムを提案し,統計特性を特徴付ける。
  論文  参考訳（メタデータ） (2021-09-09T17:24:15Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Batched Thompson Sampling for Multi-Armed Bandits [9.467098519620263]
  本稿では,トンプソンサンプリングアルゴリズムを用いて,バッチ環境でのマルチアームバンディットについて検討する。 本稿では,合成データセットと実データセットの両方で実験を行い,その効果を実証する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-08-15T20:47:46Z)
• A Change-Detection Based Thompson Sampling Framework for Non-Stationary Bandits [7.012710335689297]
  本研究では,非定常な2本腕バンディットフレームワークについて検討し,変化検出に基づくトンプソンサンプリングアルゴリズムを提案する。 提案手法は、腕の最近の報酬の経験的平均と、その歴史から得られる報酬の平均を推定する。 無線ネットワークにおける無線アクセス技術 (RAT) の選択をエッジ制御するために, TS-CDの有効性を検証する。
  論文  参考訳（メタデータ） (2020-09-06T18:12:25Z)
• Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
  部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。 局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
  論文  参考訳（メタデータ） (2020-06-17T05:48:33Z)

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

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