論文の概要: A General Theory of the Stochastic Linear Bandit and Its Applications
- arxiv url: http://arxiv.org/abs/2002.05152v4
- Date: Thu, 31 Mar 2022 22:56:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 19:19:53.180241
- Title: A General Theory of the Stochastic Linear Bandit and Its Applications
- Title（参考訳）: 確率線形帯域の一般理論とその応用
- Authors: Nima Hamidi, Mohsen Bayati
- Abstract要約: 本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。
予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。
SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
- 参考スコア（独自算出の注目度）: 8.071506311915398
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent growing adoption of experimentation in practice has led to a surge of
attention to multiarmed bandits as a technique to reduce the opportunity cost
of online experiments. In this setting, a decision-maker sequentially chooses
among a set of given actions, observes their noisy rewards, and aims to
maximize her cumulative expected reward (or minimize regret) over a horizon of
length $T$. In this paper, we introduce a general analysis framework and a
family of algorithms for the stochastic linear bandit problem that includes
well-known algorithms such as the
optimism-in-the-face-of-uncertainty-linear-bandit (OFUL) and Thompson sampling
(TS) as special cases. Our analysis technique bridges several streams of prior
literature and yields a number of new results. First, our new notion of
optimism in expectation gives rise to a new algorithm, called sieved greedy
(SG) that reduces the overexploration problem in OFUL. SG utilizes the data to
discard actions with relatively low uncertainty and then choosing one among the
remaining actions greedily. In addition to proving that SG is theoretically
rate optimal, our empirical simulations show that SG outperforms existing
benchmarks such as greedy, OFUL, and TS. The second application of our general
framework is (to the best of our knowledge) the first polylogarithmic (in $T$)
regret bounds for OFUL and TS, under similar conditions as the ones by
Goldenshluger and Zeevi (2013). Finally, we obtain sharper regret bounds for
the $k$-armed contextual MABs by a factor of $\sqrt{k}$.
- Abstract（参考訳）: 近年、実験が実際に採用されるようになると、オンライン実験の機会コストを削減する技術として、マルチアームのバンディットに注目が集まっている。
この設定において、意思決定者は、与えられた一連のアクションの中から順次選択し、彼らの騒がしい報酬を観察し、その累積的な期待報酬(または後悔を最小限に抑える)を最大化することを目指している。
本稿では,OFUL(Optimism-in-the-the-face-of-uncertainty-linear-bandit)やTS(Thompson sample)などのよく知られたアルゴリズムを含む確率線形帯域問題に対する一般解析フレームワークとアルゴリズム群を紹介する。
この分析手法は,いくつかの先行文献を橋渡しし,新たな結果をもたらす。
まず、期待における楽観主義という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。
SGはデータを利用して、比較的低い不確実性でアクションを破棄し、残ったアクションのうちの1つを選択する。
SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
私たちの一般的なフレームワークの2つ目の応用は(私たちの知る限りでは)、goldenshluger と zeevi (2013) のものと似た条件下で、oful と ts に対する最初の多対数($t$)の後悔の限界である。
最後に、$k$ の文脈MABに対して $\sqrt{k}$ の係数でよりシャープな後悔境界を得る。
関連論文リスト
- 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) - Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds [12.699376765058137]
勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
論文 参考訳（メタデータ） (2023-06-21T18:14:44Z) - 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) - Finite-Time Regret of Thompson Sampling Algorithms for Exponential
Family Multi-Armed Bandits [88.21288104408556]
本研究では,指数関数族バンドイットに対するトンプソンサンプリング (TS) アルゴリズムの遺残について検討する。
最適な腕の過小評価を避けるために,新しいサンプリング分布を用いたトンプソンサンプリング(Expulli)を提案する。
論文 参考訳（メタデータ） (2022-06-07T18:08:21Z) - Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。
類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
論文 参考訳（メタデータ） (2022-02-27T13:25:01Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Lenient Regret and Good-Action Identification in Gaussian Process
Bandits [43.03669155559218]
我々は、あるしきい値を超える関数値が「十分良い」という緩和された最適化基準の下で、ガウス過程(GP)バンディットの問題を研究する。
実用面では、既知のしきい値に従って1つの「良い行動」を見つけることの問題を考えるとともに、しきい値の知識を生かしたいくつかの善行動識別アルゴリズムを導入する。
論文 参考訳（メタデータ） (2021-02-11T01:16:58Z) - Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed
Rewards [24.983866845065926]
我々は、重い尾の報酬を持つマルチアームのバンディットを考えており、そのp$-thのモーメントは、定数$nu_p$が1pleq2$である。
本稿では,従来の情報として$nu_p$を必要としない新しいロバストな推定器を提案する。
提案した推定器の誤差確率は指数関数的に高速に減衰することを示す。
論文 参考訳（メタデータ） (2020-10-24T10:44:02Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。