論文の概要: Sparsity-Agnostic Lasso Bandit
- arxiv url: http://arxiv.org/abs/2007.08477v2
- Date: Wed, 28 Apr 2021 06:04:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 22:24:03.518175
- Title: Sparsity-Agnostic Lasso Bandit
- Title（参考訳）: Sparsity-Agnostic Lasso Bandit
- Authors: Min-hwan Oh, Garud Iyengar, Assaf Zeevi
- Abstract要約: 特徴ベクトルの次元$d$が潜在的に大きいような文脈的包帯問題を考える。
スパースブレイディットのための既存のアルゴリズムはすべて、スパーシティインデックス$s_$の値に関する事前知識を必要とする。
本稿では,スパーシティ指数$s_$の事前知識を必要としないアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 27.383079108028074
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We consider a stochastic contextual bandit problem where the dimension $d$ of
the feature vectors is potentially large, however, only a sparse subset of
features of cardinality $s_0 \ll d$ affect the reward function. Essentially all
existing algorithms for sparse bandits require a priori knowledge of the value
of the sparsity index $s_0$. This knowledge is almost never available in
practice, and misspecification of this parameter can lead to severe
deterioration in the performance of existing methods. The main contribution of
this paper is to propose an algorithm that does not require prior knowledge of
the sparsity index $s_0$ and establish tight regret bounds on its performance
under mild conditions. We also comprehensively evaluate our proposed algorithm
numerically and show that it consistently outperforms existing methods, even
when the correct sparsity index is revealed to them but is kept hidden from our
algorithm.
- Abstract（参考訳）: 特徴ベクトルの次元$d$が潜在的に大きい確率的文脈的包帯問題を考えるが、濃度$s_0 \ll d$は報酬関数に影響を与える。
本質的に、スパースバンドイットに対する既存のアルゴリズムはすべて、スパース性指数 $s_0$ の事前知識を必要とする。
この知識は実際にはほとんど利用できず、パラメータの誤特定は既存の手法の性能を著しく劣化させる可能性がある。
本研究の主な貢献は,スパーシティ指数$s_0$の事前知識を必要としないアルゴリズムを提案し,軽度条件下での性能に厳密な後悔関係を確立することである。
また,提案アルゴリズムを数値的に総合的に評価し,本手法が既存の手法を一貫して上回ることを示す。
関連論文リスト
- Lasso Bandit with Compatibility Condition on Optimal Arm [10.216425987201333]
文脈特徴のスパース部分のみが期待される報酬関数に影響を及ぼすような疎線型バンドイット問題を考える。
本稿では,強制サンプリング手法を適用したアルゴリズムを提案し,提案アルゴリズムが$O(textpolylog dT)$ regretを達成したことを証明した。
論文 参考訳（メタデータ） (2024-06-02T18:11:47Z) - Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。
UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。
我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文 参考訳（メタデータ） (2024-05-24T04:11:58Z) - 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) - Stochastic Direct Search Method for Blind Resource Allocation [6.574808513848414]
線形制約付きおよび微分自由最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。
直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。
そこで本研究では,T2/3$のオーダを後悔させるようなダイレクトサーチの簡単な拡張を提案する。
論文 参考訳（メタデータ） (2022-10-11T07:40:45Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。
本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。
提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
論文 参考訳（メタデータ） (2021-11-09T09:00:02Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Lenient Regret and Good-Action Identification in Gaussian Process
Bandits [43.03669155559218]
我々は、あるしきい値を超える関数値が「十分良い」という緩和された最適化基準の下で、ガウス過程(GP)バンディットの問題を研究する。
実用面では、既知のしきい値に従って1つの「良い行動」を見つけることの問題を考えるとともに、しきい値の知識を生かしたいくつかの善行動識別アルゴリズムを導入する。
論文 参考訳（メタデータ） (2021-02-11T01:16:58Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Entropy Regularized Power k-Means Clustering [21.013169939337583]
本稿では、クローズドフォーム更新と収束保証を享受できるスケーラブルな大規模化最小化アルゴリズムを提案する。
我々の手法は、$k$-meansと$k$-meansと同じ計算量を維持しているが、どちらも大幅に改善されている。
論文 参考訳（メタデータ） (2020-01-10T14:05:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。