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

• arxiv url: http://arxiv.org/abs/2311.01327v1
• Date: Thu, 2 Nov 2023 15:40:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-11-03 13:00:22.499210
• Title: High-dimensional Linear Bandits with Knapsacks
• Title（参考訳）: ナップサック付き高次元リニアバンディット
• Authors: Wanteng Ma, Dong Xia and Jiashuo Jiang
• Abstract要約: 特徴量が大きい高次元条件下で,knapsack (CBwK) 問題を用いた文脈的帯域幅について検討した。 本研究では,スパース推定をオンラインで行うハードしきい値アルゴリズムのオンライン版を開発する。 この統合されたアプローチは、特徴次元に対数的に依存するサブリニアな後悔を達成できることを示す。
• 参考スコア（独自算出の注目度）: 8.862707047517913
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the contextual bandits with knapsack (CBwK) problem under the high-dimensional setting where the dimension of the feature is large. The reward of pulling each arm equals the multiplication of a sparse high-dimensional weight vector and the feature of the current arrival, with additional random noise. In this paper, we investigate how to exploit this sparsity structure to achieve improved regret for the CBwK problem. To this end, we first develop an online variant of the hard thresholding algorithm that performs the sparse estimation in an online manner. We further combine our online estimator with a primal-dual framework, where we assign a dual variable to each knapsack constraint and utilize an online learning algorithm to update the dual variable, thereby controlling the consumption of the knapsack capacity. We show that this integrated approach allows us to achieve a sublinear regret that depends logarithmically on the feature dimension, thus improving the polynomial dependency established in the previous literature. We also apply our framework to the high-dimension contextual bandit problem without the knapsack constraint and achieve optimal regret in both the data-poor regime and the data-rich regime. We finally conduct numerical experiments to show the efficient empirical performance of our algorithms under the high dimensional setting.
• Abstract（参考訳）: 特徴量が大きい高次元条件下で,knapsack (CBwK) 問題を用いた文脈的帯域幅について検討した。 各腕を引っ張る報酬は、わずかな高次元の重みベクトルの乗算と現在の到着の特徴に等しく、追加のランダムノイズを伴う。 本稿では,この空間構造を利用してCBWK問題に対する後悔を改善する方法について検討する。 そこで,我々はまず,オンライン方式でスパース推定を行うハードしきい値アルゴリズムのオンライン版を開発した。 さらに、オンライン推定器と原始双対フレームワークを組み合わせることで、各knapsack制約に2つの変数を割り当て、オンライン学習アルゴリズムを用いて2つの変数を更新し、knapsackの容量を制御します。 この統合アプローチにより,特徴次元に対数的に依存する部分線形後悔が達成できることを示し,従来の文献で確立された多項式依存性を改善した。 また,クナップサック制約を伴わない高次元コンテキストバンディット問題に適用し,データポーア・レジームとデータリッチ・レジームの両方において最適な後悔を実現する。 最終的に,高次元環境下でのアルゴリズムの効率的な実験性能を示す数値実験を行った。

関連論文リスト

• 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)

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

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