論文の概要: An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling

• arxiv url: http://arxiv.org/abs/2006.04012v3
• Date: Sat, 5 Jun 2021 22:35:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 07:29:57.553792
• Title: An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
• Title（参考訳）: 一般化線形帯域の効率的なアルゴリズム:オンライン確率勾配とトンプソンサンプリング
• Authors: Qin Ding, Cho-Jui Hsieh, James Sharpnack
• Abstract要約: プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
• 参考スコア（独自算出の注目度）: 83.48992319018147
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the contextual bandit problem, where a player sequentially makes decisions based on past observations to maximize the cumulative reward. Although many algorithms have been proposed for contextual bandit, most of them rely on finding the maximum likelihood estimator at each iteration, which requires $O(t)$ time at the $t$-th iteration and are memory inefficient. A natural way to resolve this problem is to apply online stochastic gradient descent (SGD) so that the per-step time and memory complexity can be reduced to constant with respect to $t$, but a contextual bandit policy based on online SGD updates that balances exploration and exploitation has remained elusive. In this work, we show that online SGD can be applied to the generalized linear bandit problem. The proposed SGD-TS algorithm, which uses a single-step SGD update to exploit past information and uses Thompson Sampling for exploration, achieves $\tilde{O}(\sqrt{T})$ regret with the total time complexity that scales linearly in $T$ and $d$, where $T$ is the total number of rounds and $d$ is the number of features. Experimental results show that SGD-TS consistently outperforms existing algorithms on both synthetic and real datasets.
• Abstract（参考訳）: プレイヤーが累積報酬を最大化するために過去の観察に基づいて順次決定を行うコンテキストバンディット問題を考える。 多くのアルゴリズムが文脈的バンディットのために提案されているが、ほとんどのアルゴリズムは各イテレーションで最大可能性推定器を見つけることに依存しており、これは$O(t)$時間で$t$-thイテレーションで必要であり、メモリ非効率である。 この問題を解決するための自然な方法は、オンライン確率勾配勾配(SGD)を適用することで、ステップごとの時間とメモリの複雑さを$t$に対して一定に抑えることができるが、探索とエクスプロイトのバランスをとるオンラインSGD更新に基づくコンテキスト的帯域幅ポリシーは、まだ解明されていない。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 提案したSGD-TSアルゴリズムは、過去の情報を活用するためにシングルステップのSGD更新を使用し、トンプソンサンプリングを用いて探索を行い、$\tilde{O}(\sqrt{T})$ regretを達成し、T$と$d$で線形にスケールするトータルタイムの複雑さにより、$T$はラウンドの総数、$d$は機能の数である。 実験の結果、SGD-TSは、合成データセットと実データセットの両方において、既存のアルゴリズムよりも一貫して優れていた。

関連論文リスト

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• 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)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Discounted Thompson Sampling for Non-Stationary Bandit Problems [13.656518163592349]
  NS-MAB(Non-stationary multi-armed bandit)問題も最近注目されている。 非定常条件の両方に対処するため,ガウシアン先行値を用いたディスカウントトンプソンサンプリング(DS-TS)を提案する。 我々のアルゴリズムは、トンプソンサンプリングに割引係数を組み込むことにより、変化に順応的に適応する。
  論文  参考訳（メタデータ） (2023-05-18T05:29:52Z)
• No Regrets for Learning the Prior in Bandits [30.478188057004175]
  $tt AdaTS$は、バンディットタスクに順次適応するトンプソンサンプリングアルゴリズムである。 $tt AdaTS$は、バンドイト問題のいくつかのクラスで効率的に実装できる完全ベイズアルゴリズムである。
  論文  参考訳（メタデータ） (2021-07-13T15:51:32Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  GPバンディットアルゴリズムの残差境界と後部分布の複雑さのトレードオフを特徴付ける方法を示す。 大域的最適化に応用したGPバンディットアルゴリズムの精度と複雑性のトレードオフを観察する。
  論文  参考訳（メタデータ） (2020-03-23T21:05:15Z)
• MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
  トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。 我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。 我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
  論文  参考訳（メタデータ） (2020-03-03T21:24:39Z)

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

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