論文の概要: Lasso Bandit with Compatibility Condition on Optimal Arm

• arxiv url: http://arxiv.org/abs/2406.00823v1
• Date: Sun, 2 Jun 2024 18:11:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 03:16:50.552441
• Title: Lasso Bandit with Compatibility Condition on Optimal Arm
• Title（参考訳）: 最適アームの適合条件付きラッソバンド
• Authors: Harin Lee, Taehyun Hwang, Min-hwan Oh,
• Abstract要約: 文脈特徴のスパース部分のみが期待される報酬関数に影響を及ぼすような疎線型バンドイット問題を考える。 本稿では,強制サンプリング手法を適用したアルゴリズムを提案し,提案アルゴリズムが$O(textpolylog dT)$ regretを達成したことを証明した。
• 参考スコア（独自算出の注目度）: 10.216425987201333
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider a stochastic sparse linear bandit problem where only a sparse subset of context features affects the expected reward function, i.e., the unknown reward parameter has sparse structure. In the existing Lasso bandit literature, the compatibility conditions together with additional diversity conditions on the context features are imposed to achieve regret bounds that only depend logarithmically on the ambient dimension $d$. In this paper, we demonstrate that even without the additional diversity assumptions, the compatibility condition only on the optimal arm is sufficient to derive a regret bound that depends logarithmically on $d$, and our assumption is strictly weaker than those used in the lasso bandit literature under the single parameter setting. We propose an algorithm that adapts the forced-sampling technique and prove that the proposed algorithm achieves $O(\text{poly}\log dT)$ regret under the margin condition. To our knowledge, the proposed algorithm requires the weakest assumptions among Lasso bandit algorithms under a single parameter setting that achieve $O(\text{poly}\log dT)$ regret. Through the numerical experiments, we confirm the superior performance of our proposed algorithm.
• Abstract（参考訳）: 我々は、文脈特徴のスパース部分のみが期待される報酬関数に影響を与える確率的スパース線形バンドイト問題、すなわち未知の報酬パラメータがスパース構造を持つことを考察する。 既存のラッソ・バンディットの文献では、文脈特徴に対する追加の多様性条件とともに、周囲次元$d$に対数的にのみ依存する後悔境界を達成するために、互換性条件が課される。 本稿では,追加の多様性仮定がなくても,最適アーム上の適合条件は$d$に対数的に依存する後悔境界を導出するのに十分であり,この仮定は単一パラメータ設定の下でラッソ・バンディット文献で用いられるものよりも厳密に弱いことを示す。 本稿では,強制サンプリング手法を適応させるアルゴリズムを提案し,提案アルゴリズムが限界条件下で$O(\text{poly}\log dT)$ regretを達成できることを示す。 我々の知る限り、提案アルゴリズムは1つのパラメータ設定の下で、Lasso banditアルゴリズムの中で最も弱い仮定を必要とし、$O(\text{poly}\log dT)$ regretを達成している。 数値実験により,提案アルゴリズムの優れた性能を確認した。

関連論文リスト

• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits [18.971564419292893]
  我々は、$O(sqrtdTlog T)$ regret boundで、$d$は文脈の次元、$T$は時間地平線であるような線形文脈的帯域幅アルゴリズムを提案する。 提案アルゴリズムは,探索を明示的ランダム化により埋め込んだ新しい推定器を備える。
  論文  参考訳（メタデータ） (2022-06-11T02:43:17Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Regret Lower Bound and Optimal Algorithm for High-Dimensional Contextual Linear Bandit [10.604939762790517]
  我々は、累積後悔に対して、$mathcalObig((log d)fracalpha+12Tfrac1-alpha2+log Tbig)$をミニマックス下界として証明する。 第2に,汎用的なアッパー信頼境界(UCB)戦略に着想を得た,シンプルで効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T19:35:38Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。 一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
  論文  参考訳（メタデータ） (2020-10-22T19:14:37Z)
• Sparsity-Agnostic Lasso Bandit [27.383079108028074]
  特徴ベクトルの次元$d$が潜在的に大きいような文脈的包帯問題を考える。 スパースブレイディットのための既存のアルゴリズムはすべて、スパーシティインデックス$s_$の値に関する事前知識を必要とする。 本稿では,スパーシティ指数$s_$の事前知識を必要としないアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-16T17:24:12Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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