論文の概要: Learning to Sparsify Stochastic Linear Bandits

• arxiv url: http://arxiv.org/abs/2605.10151v1
• Date: Mon, 11 May 2026 07:57:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.622266
• Title: Learning to Sparsify Stochastic Linear Bandits
• Title（参考訳）: 確率線形帯域分散の学習
• Authors: Zhengmiao Wang, Ming Chi, Zhi-Wei Liu, Lintao Ye, Carla Fabiana Chiasserini,
• Abstract要約: 本稿では,高次元空間から連続的に行動を選択する線形帯域幅の分散化を学習する問題に対処する。 本稿では,パラメータ学習のための最小二乗法と,スパース動作選択のための特別サブルーチンを用いて,適応的に段階的に探索・利用を行うアルゴリズムフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 12.61900668356141
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a $\tilde{\mathcal{O}}(d\sqrt{T})$ regret, where $d$ is the dimension of the action vector and $T$ is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a $\tilde{\mathcal{O}}(d \sqrt{T})$ $α$-regret; for general compact sets lacking strong convexity, we establish a $\tilde{\mathcal{O}}(d T^{2/3})$ $α$-regret, where $α$ pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.
• Abstract（参考訳）: 本稿では, 確率的線形帯域幅の分散化を学習する問題に対処する。これは, ベクトルの非零元数に対する空間の分散制約を考慮した高次元空間からのアクションを逐次選択する。 鍵となる課題は、累積的後悔を最小限に抑えながら、問題の固有の組合せ構造に起因する最適なスパース行動を見つけるNP硬度に対処することである。 本稿では,パラメータ学習のための最小二乗法と,スパース動作選択のための特別サブルーチンを用いて,適応的に段階的に探索・利用を行うアルゴリズムフレームワークを提案する。 作用集合がユークリッド球の場合、最適なスパース作用を効率的に計算することができ、$\tilde{\mathcal{O}}(d\sqrt{T})$ regret を成立させることができる。 最適スパース作用を求めるような一般凸およびコンパクトな作用集合に対しては、グリーディ・サブルーチンを用いる。 一般の強凸作用集合に対しては、$\tilde{\mathcal{O}}(d \sqrt{T})$$α$-regretを導出する; 強凸性を持たない一般コンパクト集合に対しては、$\tilde{\mathcal{O}}(d T^{2/3})$$$α$-regretを確立する。 最後に,提案手法の適用を含む広範囲な実験により,アルゴリズムの性能を検証した。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits [16.103685478563072]
  本稿では,一般制約付き線形帯域について考察する。 目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。 本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-10T07:30:37Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)

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

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