論文の概要: 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の容量を制御します。 この統合アプローチにより,特徴次元に対数的に依存する部分線形後悔が達成できることを示し,従来の文献で確立された多項式依存性を改善した。 また,クナップサック制約を伴わない高次元コンテキストバンディット問題に適用し,データポーア・レジームとデータリッチ・レジームの両方において最適な後悔を実現する。 最終的に,高次元環境下でのアルゴリズムの効率的な実験性能を示す数値実験を行った。

関連論文リスト

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

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

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