論文の概要: Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis

• arxiv url: http://arxiv.org/abs/2002.11332v1
• Date: Wed, 26 Feb 2020 07:29:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 14:32:57.309142
• Title: Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis
• Title（参考訳）: 構造付き線形コンテキスト帯域:シャープと幾何学的スムース解析
• Authors: Vidyashankar Sivakumar, Zhiwei Steven Wu, Arindam Banerjee
• Abstract要約: 本稿では,ガウス雑音によって逆向きの文脈が乱されるような構造付き線形文脈帯域のスムーズな設定について考察する。 単純な欲求アルゴリズムが機能するスムーズな環境では暗黙的な探索が存在することを示す。
• 参考スコア（独自算出の注目度）: 48.25118610209545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandit learning algorithms typically involve the balance of exploration and exploitation. However, in many practical applications, worst-case scenarios needing systematic exploration are seldom encountered. In this work, we consider a smoothed setting for structured linear contextual bandits where the adversarial contexts are perturbed by Gaussian noise and the unknown parameter $\theta^*$ has structure, e.g., sparsity, group sparsity, low rank, etc. We propose simple greedy algorithms for both the single- and multi-parameter (i.e., different parameter for each context) settings and provide a unified regret analysis for $\theta^*$ with any assumed structure. The regret bounds are expressed in terms of geometric quantities such as Gaussian widths associated with the structure of $\theta^*$. We also obtain sharper regret bounds compared to earlier work for the unstructured $\theta^*$ setting as a consequence of our improved analysis. We show there is implicit exploration in the smoothed setting where a simple greedy algorithm works.
• Abstract（参考訳）: バンディット学習アルゴリズムは通常、探索と搾取のバランスを伴う。 しかし、多くの実践的応用において、系統的な探索を必要とする最悪のシナリオはほとんど遭遇しない。 本研究では,逆文脈がガウス雑音によって摂動し,未知パラメータ$\theta^*$ が構造,例えばスパーシティ,グループスパーシティ,低ランクなどを持つ構造線形文脈バンディットに対する平滑化設定を考える。 単一パラメータと複数パラメータ(文脈ごとに異なるパラメータ)の設定に対して単純なグリージーアルゴリズムを提案し、仮定された構造を持つ$\theta^*$に対する統一的後悔解析を提供する。 後悔の境界は、{\theta^*$ の構造に付随するガウス幅のような幾何学的量で表現される。 また,未構造化の$\theta^*$ 設定に対する従来の作業と比較して,より鋭い後悔の限界を得ることができた。 単純な欲望アルゴリズムが動作する滑らかな設定には暗黙の探索があることを示す。

関連論文リスト

• Lasso Bandit with Compatibility Condition on Optimal Arm [10.216425987201333]
  文脈特徴のスパース部分のみが期待される報酬関数に影響を及ぼすような疎線型バンドイット問題を考える。 本稿では,強制サンプリング手法を適用したアルゴリズムを提案し,提案アルゴリズムが$O(textpolylog dT)$ regretを達成したことを証明した。
  論文  参考訳（メタデータ） (2024-06-02T18:11:47Z)
• 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)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• 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)
• A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem [25.5073029104128]
  簡単なオンラインのLassoは、残酷な$mathcalO(sqrtkTlog d)$で、疎線形コンテキストバンドリットをサポートすることを証明している。 この結果の特別な構造は、摂動が探査期間にどのように影響するかを明確に特徴付ける。
  論文  参考訳（メタデータ） (2020-07-16T18:48:45Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• Regret Minimization in Stochastic Contextual Dueling Bandits [40.17224226373741]
  我々は、コンテキスト設定において、$K$武装デュエルバンディットの問題を考察する。 提案手法は, それぞれ, 後悔の保証を施した2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-20T06:36:19Z)

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

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