論文の概要: Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret
in Stochastic Contextual Linear Bandits
- arxiv url: http://arxiv.org/abs/2205.09899v1
- Date: Thu, 19 May 2022 23:41:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-23 13:14:44.804919
- Title: Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret
in Stochastic Contextual Linear Bandits
- Title（参考訳）: $\sqrt{T}$ Barrier: 確率的文脈線形帯域におけるインスタンス独立な対数レグレットを破る
- Authors: Avishek Ghosh and Abishek Sankararaman
- Abstract要約: 線形ペイオフを伴う文脈的包帯に対する対数的後悔(多元的後悔)を証明した。
コンテキストは、$sqrtT$から$polylog(T)$への後悔を減らすのに役立ちます。
- 参考スコア（独自算出の注目度）: 10.127456032874978
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove an instance independent (poly) logarithmic regret for stochastic
contextual bandits with linear payoff. Previously, in \cite{chu2011contextual},
a lower bound of $\mathcal{O}(\sqrt{T})$ is shown for the contextual linear
bandit problem with arbitrary (adversarily chosen) contexts. In this paper, we
show that stochastic contexts indeed help to reduce the regret from $\sqrt{T}$
to $\polylog(T)$. We propose Low Regret Stochastic Contextual Bandits
(\texttt{LR-SCB}), which takes advantage of the stochastic contexts and
performs parameter estimation (in $\ell_2$ norm) and regret minimization
simultaneously. \texttt{LR-SCB} works in epochs, where the parameter estimation
of the previous epoch is used to reduce the regret of the current epoch. The
(poly) logarithmic regret of \texttt{LR-SCB} stems from two crucial facts: (a)
the application of a norm adaptive algorithm to exploit the parameter
estimation and (b) an analysis of the shifted linear contextual bandit
algorithm, showing that shifting results in increasing regret. We have also
shown experimentally that stochastic contexts indeed incurs a regret that
scales with $\polylog(T)$.
- Abstract（参考訳）: 線形ペイオフを伴う確率的文脈的バンディットに対するインスタンス独立(多)対数的後悔を証明する。
以前は、$\mathcal{O}(\sqrt{T})$ の下界は任意の(逆選択された)文脈を持つ文脈線形帯域問題に対して示されていた。
本稿では,確率的文脈が,その後悔を$\sqrt{T}$から$\polylog(T)$に減らすのに役立つことを示す。
本稿では,確率的文脈を活かし,パラメータ推定($\ell_2$ norm)と後悔最小化を同時に行う低レグレト確率的文脈帯域(\texttt{LR-SCB})を提案する。
\textt{lr-scb} は、以前のエポックのパラメータ推定が現在のエポックの後悔を減らすために使用されるエポックで動作する。
texttt{LR-SCB} の(多分)対数的後悔は2つの重要な事実に由来する。
(a)パラメータ推定とパラメータ推定のためのノルム適応アルゴリズムの適用
(b) シフトした線形文脈帯域幅アルゴリズムの解析により, シフトが後悔を増すことを示した。
我々はまた、確率的文脈が実際に$\polylog(T)$でスケールする後悔を引き起こすことを実験的に示した。
関連論文リスト
- An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - 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) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Online nonparametric regression with Sobolev kernels [99.12817345416846]
我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。
上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
論文 参考訳（メタデータ） (2021-02-06T15:05:14Z) - Doubly robust Thompson sampling for linear payoffs [12.375561840897742]
本稿では,Douubly Robust (DR) Thompson Sampling と呼ばれる新しいマルチアームコンテキスト帯域幅アルゴリズムを提案する。
提案アルゴリズムは, 新たな補遺分解を許容し, $tildeO(phi-2sqrtT)$の順序で補遺を改良する。
論文 参考訳（メタデータ） (2021-02-01T23:31:10Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。