論文の概要: Non-stationary Bandits with Knapsacks
- arxiv url: http://arxiv.org/abs/2205.12427v1
- Date: Wed, 25 May 2022 01:22:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-26 13:38:16.671382
- Title: Non-stationary Bandits with Knapsacks
- Title（参考訳）: ナップサック付き非定常バンディット
- Authors: Shang Liu, Jiashuo Jiang, Xiaocheng Li
- Abstract要約: 非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
- 参考スコア（独自算出の注目度）: 6.2006721306998065
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of bandits with knapsacks (BwK) in a
non-stationary environment. The BwK problem generalizes the multi-arm bandit
(MAB) problem to model the resource consumption associated with playing each
arm. At each time, the decision maker/player chooses to play an arm, and s/he
will receive a reward and consume certain amount of resource from each of the
multiple resource types. The objective is to maximize the cumulative reward
over a finite horizon subject to some knapsack constraints on the resources.
Existing works study the BwK problem under either a stochastic or adversarial
environment. Our paper considers a non-stationary environment which
continuously interpolates between these two extremes. We first show that the
traditional notion of variation budget is insufficient to characterize the
non-stationarity of the BwK problem for a sublinear regret due to the presence
of the constraints, and then we propose a new notion of global non-stationarity
measure. We employ both non-stationarity measures to derive upper and lower
bounds for the problem. Our results are based on a primal-dual analysis of the
underlying linear programs and highlight the interplay between the constraints
and the non-stationarity. Finally, we also extend the non-stationarity measure
to the problem of online convex optimization with constraints and obtain new
regret bounds accordingly.
- Abstract（参考訳）: 本稿では,非定常環境におけるknapsacks (BwK) による包帯問題について検討する。
BwK問題は、マルチアームバンディット(MAB)問題を一般化し、各アームの演奏に伴うリソース消費をモデル化する。
各タイミングで、意思決定者/プレーヤはアームをプレイすることを選択し、s/heは報酬を受け取り、複数のリソースタイプから特定のリソースを消費する。
目的は資源上のいくつかのクナップサック制約を受ける有限地平線上の累積報酬を最大化することである。
既存の研究は、BwK問題を確率的あるいは敵対的な環境下で研究している。
本稿では,この2つの極端を補間する非定常環境について考察する。
まず, 従来の変動予算の概念は, 制約の存在によるサブ線形後悔に対するBwK問題の非定常性を特徴づけるには不十分であることを示すとともに, グローバルな非定常度尺度の新たな概念を提案する。
我々は,この問題の上限と下限を導出するために,非定常尺度を併用する。
本研究は,基礎となる線形プログラムの基本双対解析に基づき,制約と非定常性の相互作用を強調する。
最後に,非定常度尺度を制約付きオンライン凸最適化の問題に拡張し,それに応じて新たな後悔境界を求める。
関連論文リスト
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals [28.94461817548213]
条件付き良性環境と任意の環境下での学習性能におけるトレードオフの可能性について,上界と下界の整合性を証明した。
この問題を線形バンディット設定に還元することで、最初に因果バンディットのインスタンス依存境界を求める。
論文 参考訳（メタデータ） (2024-07-01T04:12:15Z) - No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。
最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。
この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
論文 参考訳（メタデータ） (2024-05-10T16:22:33Z) - Bandits with Replenishable Knapsacks: the Best of both Worlds [26.786438972889208]
非単調な資源利用を可能にするBwKフレームワークの自然な一般化について検討する。
入力モデルの下で、我々のアルゴリズムはインスタンスに依存しない $tildeO(T1/2)$ regret bound を生成する。
論文 参考訳（メタデータ） (2023-06-14T12:34:00Z) - 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) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。
本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。
本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2022-03-29T14:02:03Z) - Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。
当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
論文 参考訳（メタデータ） (2022-02-28T12:10:48Z) - Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits [66.02233330016435]
後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-10-12T03:24:57Z) - The Symmetry between Bandits and Knapsacks: A Primal-Dual LP-based
Approach [15.626602292752624]
そこで我々は,問題依存型対数的後悔境界を実現する原始双対アルゴリズムを開発した。
サブオプティマティリティ尺度は、後悔を決定する上でのナップサックの重要な役割を強調します。
これは一般のBwK問題を解くための最初の問題依存対数的後悔である。
論文 参考訳（メタデータ） (2021-02-12T08:14:30Z) - Coordinated Online Learning for Multi-Agent Systems with Coupled
Constraints and Perturbed Utility Observations [91.02019381927236]
本研究では, 資源制約を満たすため, エージェントを安定な集団状態へ誘導する新しい手法を提案する。
提案手法は,ゲームラグランジアンの拡張によるリソース負荷に基づく分散リソース価格設定手法である。
論文 参考訳（メタデータ） (2020-10-21T10:11:17Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。