論文の概要: High-dimensional Linear Bandits with Knapsacks

• arxiv url: http://arxiv.org/abs/2311.01327v2
• Date: Sat, 02 Aug 2025 07:21:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:21.503839
• Title: High-dimensional Linear Bandits with Knapsacks
• Title（参考訳）: クナップサックを用いた高次元線形帯域
• Authors: Wanteng Ma, Dong Xia, Jiashuo Jiang,
• Abstract要約: 本研究では,スパース推定をオンラインで行うハードしきい値アルゴリズムのオンライン版を開発する。 以下の構造的仮定のいずれかが、よりシャープな後悔境界である$tildeO(s_0 sqrtT)$に対して十分であることを示す。 副産物として、クナップサック制約を伴わない高次元のコンテキスト帯域に我々のフレームワークを適用することで、データポーラとデータリッチレジームの両方において最適な後悔率を回復する。
• 参考スコア（独自算出の注目度）: 7.8856737627153874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the contextual bandits with knapsack (CBwK) problem in a high-dimensional linear setting, where the feature dimension can be very large. Our goal is to harness sparsity to obtain sharper regret guarantees. To this end, we first develop an online variant of the hard thresholding algorithm that performs the sparse estimation in an online manner. We then embed this estimator in a primal-dual scheme: every knapsack constraint is paired with a dual variable, which is updated by an online learning rule to keep the cumulative resource consumption within budget. This integrated approach achieves a two-phase sub-linear regret that scales only logarithmically with the feature dimension, improving on the polynomial dependency reported in prior work. Furthermore, we show that either of the following structural assumptions is sufficient for a sharper regret bound of $\tilde{O}(s_{0} \sqrt{T})$: (i) a diverse-covariate condition; and (ii) a margin condition. When both conditions hold simultaneously, we can further control the regret to $O(s_{0}^{2} \log(dT)\log T)$ by a dual resolving scheme. As a by-product, applying our framework to high-dimensional contextual bandits without knapsack constraints recovers the optimal regret rates in both the data-poor and data-rich regimes. Finally, numerical experiments confirm the empirical efficiency of our algorithms in high-dimensional settings.
• Abstract（参考訳）: 本研究では,高次元線形設定におけるknapsack (CBwK) 問題による文脈的帯域幅について検討する。 我々の目標は、忍耐力を活用して、より厳しい後悔の保証を得ることです。 この目的のために、我々はまず、スパース推定をオンラインで行うハードしきい値アルゴリズムのオンライン版を開発する。 各knapsack制約は、オンライン学習ルールによって更新され、累積的なリソース消費を予算内に保持する。 この統合アプローチは、特徴次元と対数的にしかスケールしない2相サブ線形後悔を達成し、以前の作業で報告された多項式依存性を改善する。 さらに、以下の構造的仮定のいずれかが$\tilde{O}(s_{0} \sqrt{T})$のよりシャープな後悔境界に対して十分であることを示す。 (i)多変量条件,及び (ii)マージン条件。 両方の条件が同時に成立すると、二重解決スキームにより$O(s_{0}^{2} \log(dT)\log T)$に対する後悔をさらに制御できる。 副産物として、クナップサック制約を伴わない高次元のコンテキスト帯域に我々のフレームワークを適用することで、データポーラとデータリッチレジームの両方において最適な後悔率を回復する。 最後に, 数値実験により, アルゴリズムの高次元設定における経験的効率を確認した。

関連論文リスト

• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
  ニューラルネットワークを利用して非線形ユーティリティ関数を近似する分散認識アルゴリズムを提案する。 十分広いニューラルネットワークに対して,我々のアルゴリズムが次数$bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt)のサブ線形累積平均後悔を達成できることを示す理論的保証を確立する。
  論文  参考訳（メタデータ） (2025-06-02T01:58:48Z)
• Sparse Additive Contextual Bandits: A Nonparametric Approach for Online Decision-making with High-dimensional Covariates [10.04289564826712]
  我々は,カーネルヒルベルト空間を再現する際の余剰加法的報酬モデルに基づく文脈的帯域幅アルゴリズムを開発した。 ランダム領域に適用した2倍のペナル化手法の統計的特性を確立し,バンディットフィードバックに基づく新たな解析手法を提案する。
  論文  参考訳（メタデータ） (2025-03-21T08:33:28Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  データ・ポーア・システマにおける高次元スパース線形包帯問題について検討する。 線形モデルに対するラッソ推定器の新たなオフライン統計的保証を示す。 本稿では,最小限のコストで最適空間パラメータ$k$の知識を必要としない相関に基づくメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-26T01:42:03Z)
• FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits [8.908421753758475]
  高次元スパース線形帯域は、シーケンシャルな意思決定問題の効率的なモデルとして機能する。 データプライバシの懸念により、我々は、共同でプライベートな高次元の疎線形帯域について検討する。 FLIPHATは,プライバシパラメータの点で最適に後悔することを示す。
  論文  参考訳（メタデータ） (2024-05-22T22:19:12Z)
• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
  本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。 最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。 この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
  論文  参考訳（メタデータ） (2024-05-10T16:22:33Z)
• 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)
• 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)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression [65.8785736964253]
  本稿では,線形制約付きコンテキスト帯域(CBwLC)について考察する。これは,アルゴリズムが全消費の線形制約を受ける複数のリソースを消費するコンテキスト帯域の変種である。 この問題はknapsacks (CBwK) を用いてコンテキスト的帯域幅を一般化し、制約のパッケージ化とカバー、および正および負のリソース消費を可能にする。 本稿では,回帰オラクルに基づくCBwLC(CBwK)のアルゴリズムについて述べる。このアルゴリズムは単純で,計算効率が良く,統計的に最適である。
  論文  参考訳（メタデータ） (2022-11-14T16:08:44Z)
• PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits [29.097522376094624]
  そこで我々はPopArtと呼ばれる単純で効率的なスパース線形推定法を提案する。 我々は, 粗い線形バンディットアルゴリズムを導出し, 美術品の状態に対する後悔の上界の改善を享受する。
  論文  参考訳（メタデータ） (2022-10-25T19:13:20Z)
• Meta-Learning Adversarial Bandits [49.094361442409785]
  本研究の目的は,複数のタスクにまたがる帯域幅フィードバックを用いてオンライン学習を学習し,タスク間の平均性能を改善することである。 敵対的設定を最初に対象とするメタアルゴリズムとして,マルチアーム・バンディット(MAB)とバンディット・最適化(BLO)の2つの重要なケースに対して,特定の保証を設定するメタアルゴリズムを設計する。 我々の保証は、非正規化されたフォローザリーダーと乗法重みを組み合わせることで、オンラインで非滑らかで非Bシーケンスを学ぶのに十分であることを示すことに依存しています。
  論文  参考訳（メタデータ） (2022-05-27T17:40:32Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• On Learning to Rank Long Sequences with Contextual Bandits [17.97356309346139]
  本稿では,様々な報酬と損失を伴うフレキシブルな長さ列を考慮したカスケーディング・バンディットモデルを提案する。 我々の分析は、バニラカスケードの盗賊に特化して、文献で以前よりも厳しい保証をもたらす厳格な後悔の限界を提供する。
  論文  参考訳（メタデータ） (2021-06-07T12:16:34Z)
• The Symmetry between Bandits and Knapsacks: A Primal-Dual LP-based Approach [15.626602292752624]
  そこで我々は,問題依存型対数的後悔境界を実現する原始双対アルゴリズムを開発した。 サブオプティマティリティ尺度は、後悔を決定する上でのナップサックの重要な役割を強調します。 これは一般のBwK問題を解くための最初の問題依存対数的後悔である。
  論文  参考訳（メタデータ） (2021-02-12T08:14:30Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Slice Sampling for General Completely Random Measures [74.24975039689893]
  本稿では, 後続推定のためのマルコフ連鎖モンテカルロアルゴリズムについて, 補助スライス変数を用いてトランケーションレベルを適応的に設定する。 提案アルゴリズムの有効性は、いくつかの一般的な非パラメトリックモデルで評価される。
  論文  参考訳（メタデータ） (2020-06-24T17:53:53Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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