Fugu-MT 論文翻訳(概要): When and why randomised exploration works (in linear bandits)

論文の概要: When and why randomised exploration works (in linear bandits)

arxiv url: http://arxiv.org/abs/2502.08870v1
Date: Thu, 13 Feb 2025 00:49:28 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-14 13:50:20.551922
Title: When and why randomised exploration works (in linear bandits)
Title（参考訳）: ランダム化探索がいつ,なぜ働くのか(線形帯域で)
Authors: Marc Abeille, David Janz, Ciara Pike-Burke,
Abstract要約: 作用空間が滑らかで凸であるとき、ランダム化された探索アルゴリズムは、$O(dsqrtn log(n))$の順序に縛られた$n$ステップの後悔を楽しむ。このことは、トンプソンサンプリングが後悔の最適次元依存を達成できるような非自明な線形バンディット設定が存在することを初めて示している。
参考スコア（独自算出の注目度）: 9.167278626563007
License:
Abstract: We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely on forced optimism or posterior inflation. With this, we demonstrate that in the $d$-dimensional linear bandit setting, when the action space is smooth and strongly convex, randomised exploration algorithms enjoy an $n$-step regret bound of the order $O(d\sqrt{n} \log(n))$. Notably, this shows for the first time that there exist non-trivial linear bandit settings where Thompson sampling can achieve optimal dimension dependence in the regret.
Abstract（参考訳）: 我々は、強制的な楽観主義や後続のインフレーションに依存しないトンプソンサンプリングのようなランダムな探索アルゴリズムを解析するためのアプローチを提供する。これにより、$d$次元線形帯域設定において、アクション空間が滑らかで凸であるとき、ランダム化された探索アルゴリズムは、$O(d\sqrt{n} \log(n))$の$n$ステップ後悔境界を享受する。このことは、トンプソンサンプリングが後悔の最適次元依存を達成できるような非自明な線形バンディット設定が存在することを初めて示している。

関連論文リスト

Exploration via linearly perturbed loss minimisation [4.856378369489158]
本稿では,構造的バンディット問題に対する線形損失摂動(EVILL)による探索を紹介する。一般化された線形包帯の場合、EVILLは乱れ歴史探索(PHE)に還元され、ランダムな乱れ報酬のトレーニングによって探索が行われる。本稿では,従来のPHE方式では存在しないデータ依存摂動について提案する。
論文参考訳（メタデータ） (2023-11-13T18:54:43Z)
Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文参考訳（メタデータ） (2023-03-17T17:53:28Z)
Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits [17.11922027966447]
この研究は、高次元およびスパースな文脈的包帯におけるトンプソンサンプリングの理論的な保証を提供する。より高速な計算のために、MCMCの代わりに未知のパラメータと変分推論をモデル化するために、スパイク・アンド・スラブを用いる。
論文参考訳（メタデータ） (2022-11-11T02:23:39Z)
Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文参考訳（メタデータ） (2022-07-23T20:25:07Z)
Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文参考訳（メタデータ） (2022-06-07T18:08:21Z)
Variational Bayesian Optimistic Sampling [43.130465039780084]
エージェントが探索と搾取のバランスをとる必要があるオンラインシーケンシャルな意思決定問題を考える。我々は、多腕バンディットの場合、トンプソンサンプリングポリシーを含むベイズ楽観的な政策の集合を導出する。楽観的な集合におけるポリシーを生成するアルゴリズムは、$T$ラウンド後の$A$アクションの問題に対して$tilde O(sqrtAT)$ Bayesian regretを楽しんでいることが示される。
論文参考訳（メタデータ） (2021-10-29T11:28:29Z)
Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文参考訳（メタデータ） (2020-09-04T04:10:39Z)
Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring [91.22679787578438]
部分モニタリングのためのトンプソンサンプリングに基づく新しいアルゴリズムを提案する。局所可観測性を持つ問題の線形化変種に対して,新たなアルゴリズムが対数問題依存の擬似回帰$mathrmO(log T)$を達成することを証明した。
論文参考訳（メタデータ） (2020-06-17T05:48:33Z)
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)
MOTS: Minimax Optimal Thompson Sampling [89.2370817955411]
トンプソンサンプリングがミニマックス下限の$Omega(sqrtKT)$と$K$の武器付きバンディット問題に一致するかどうかという未解決の問題のままである。我々は,各タイミングで選択した腕のサンプリングインスタンスを適応的にクリップするMOTSと呼ばれるトンプソンサンプリングの変種を提案する。我々は、この単純なトンプソンサンプリングの変種が、有限時間地平線に対して$O(sqrtKT)$のミニマックス最適後悔境界と、$T$が無限に近づくときのガウス報酬に対する最適後悔境界を達成することを証明した。
論文参考訳（メタデータ） (2020-03-03T21:24:39Z)

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