論文の概要: Thresholded Lasso Bandit

• arxiv url: http://arxiv.org/abs/2010.11994v4
• Date: Sun, 19 Jun 2022 08:37:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 05:38:10.757222
• Title: Thresholded Lasso Bandit
• Title（参考訳）: 閾値付きラッソ・バンディット
• Authors: Kaito Ariu, Kenshi Abe, Alexandre Prouti\`ere
• Abstract要約: Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
• 参考スコア（独自算出の注目度）: 70.17389393497125
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we revisit the regret minimization problem in sparse stochastic contextual linear bandits, where feature vectors may be of large dimension $d$, but where the reward function depends on a few, say $s_0\ll d$, of these features only. We present Thresholded Lasso bandit, an algorithm that (i) estimates the vector defining the reward function as well as its sparse support, i.e., significant feature elements, using the Lasso framework with thresholding, and (ii) selects an arm greedily according to this estimate projected on its support. The algorithm does not require prior knowledge of the sparsity index $s_0$ and can be parameter-free under some symmetric assumptions. For this simple algorithm, we establish non-asymptotic regret upper bounds scaling as $\mathcal{O}( \log d + \sqrt{T} )$ in general, and as $\mathcal{O}( \log d + \log T)$ under the so-called margin condition (a probabilistic condition on the separation of the arm rewards). The regret of previous algorithms scales as $\mathcal{O}( \log d + \sqrt{T \log (d T)})$ and $\mathcal{O}( \log T \log d)$ in the two settings, respectively. Through numerical experiments, we confirm that our algorithm outperforms existing methods.
• Abstract（参考訳）: 本稿では,特徴ベクトルが大きめの次元$d$である場合,例えば$s_0\ll d$のような報酬関数にのみ依存する場合において,スパース確率的文脈線形包帯における後悔の最小化問題を再検討する。 私たちはThresholded Lasso banditというアルゴリズムを紹介します。 (i)報酬関数を定義するベクトルとそのスパースサポート、すなわち重要な特徴要素をしきい値付きlassoフレームワークを用いて推定する。 (二)その支持に投じられたこの推定に従って腕を優しく選別する。 このアルゴリズムはスパーシティ指数 $s_0$ の事前知識を必要とせず、いくつかの対称的な仮定の下でパラメータフリーとなる。 この単純なアルゴリズムでは、一般に$\mathcal{O}( \log d + \sqrt{T} )$、いわゆるマージン条件の下で$\mathcal{O}( \log d + \log T)$としてスケールする非漸近的後悔の上界(腕の報酬の分離に関する確率的条件)を確立する。 以前のアルゴリズムの後悔は、2つの設定でそれぞれ$\mathcal{O}( \log d + \sqrt{T \log (d T)})$と$\mathcal{O}( \log T \log d)$にスケールする。 数値実験により,本アルゴリズムが既存手法より優れていることを確認した。

関連論文リスト

• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• 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)
• Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise [45.60098988395789]
  マルチアームバンディットのためのUCB型アルゴリズムを構築するための新しいアルゴリズムを提案する。 報酬の対称雑音の場合、$O(log TsqrtKTlog T)$ regret bound を $Oleft の代わりに達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-10T22:38:21Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Optimal Contextual Pricing and Extensions [32.152826900874075]
  このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。 これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
  論文  参考訳（メタデータ） (2020-03-03T18:46:29Z)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
  論文  参考訳（メタデータ） (2020-01-25T14:44:53Z)

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

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