論文の概要: The Symmetry between Bandits and Knapsacks: A Primal-Dual LP-based
Approach
- arxiv url: http://arxiv.org/abs/2102.06385v1
- Date: Fri, 12 Feb 2021 08:14:30 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-15 12:59:33.288122
- Title: The Symmetry between Bandits and Knapsacks: A Primal-Dual LP-based
Approach
- Title（参考訳）: バンディットとナップサックの対称性:プライマリデュアルLPベースのアプローチ
- Authors: Xiaocheng Li, Chunlin Sun, Yinyu Ye
- Abstract要約: そこで我々は,問題依存型対数的後悔境界を実現する原始双対アルゴリズムを開発した。
サブオプティマティリティ尺度は、後悔を決定する上でのナップサックの重要な役割を強調します。
これは一般のBwK問題を解くための最初の問題依存対数的後悔である。
- 参考スコア（独自算出の注目度）: 15.626602292752624
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the bandits with knapsacks (BwK) problem and develop
a primal-dual based algorithm that achieves a problem-dependent logarithmic
regret bound. The BwK problem extends the multi-arm bandit (MAB) problem to
model the resource consumption associated with playing each arm, and the
existing BwK literature has been mainly focused on deriving asymptotically
optimal distribution-free regret bounds. We first study the primal and dual
linear programs underlying the BwK problem. From this primal-dual perspective,
we discover symmetry between arms and knapsacks, and then propose a new notion
of sub-optimality measure for the BwK problem. The sub-optimality measure
highlights the important role of knapsacks in determining algorithm regret and
inspires the design of our two-phase algorithm. In the first phase, the
algorithm identifies the optimal arms and the binding knapsacks, and in the
second phase, it exhausts the binding knapsacks via playing the optimal arms
through an adaptive procedure. Our regret upper bound involves the proposed
sub-optimality measure and it has a logarithmic dependence on length of horizon
$T$ and a polynomial dependence on $m$ (the numbers of arms) and $d$ (the
number of knapsacks). To the best of our knowledge, this is the first
problem-dependent logarithmic regret bound for solving the general BwK problem.
- Abstract（参考訳）: 本稿では,knapsacks (BwK) 問題を用いた盗賊について検討し,問題依存の対数的後悔境界を実現する原始双対アルゴリズムを開発した。
BwK問題は、各アームの演奏に伴う資源消費をモデル化するためにマルチアーム・バンディット(MAB)問題を拡張しており、既存のBwK文献は主に漸近的に最適な分布のない後悔境界の導出に重点を置いている。
まず、BwK問題の基礎となるプライマリ線形およびデュアル線形プログラムを研究する。
この原始双対的な観点から、アームとクナプサックの対称性を発見し、BwK問題に対する準最適測度の新しい概念を提案する。
サブオプティリティ尺度は,アルゴリズムの後悔判定におけるナップサックの役割を強調し,二相アルゴリズムの設計を刺激する。
第1段階では、アルゴリズムは最適なアームと結合クナプサックを識別し、第2段階では適応的な手順で最適なアームを演奏することで結合クナプサックを排気する。
我々の後悔の上限は、提案された準最適測度であり、horizon $t$の長さの対数依存性と、$m$(腕の数)と$d$(ナップサックの数)の多項式依存性がある。
我々の知る限りでは、これは一般のBwK問題を解くための最初の問題依存対数的後悔である。
関連論文リスト
- Replicability is Asymptotically Free in Multi-armed Bandits [45.729105054410745]
この仕事の動機は、再現可能な機械学習の需要の増加にある。
特に、高い確率で、アルゴリズムのアクション列がデータセットに固有のランダム性の影響を受けないように、複製可能なアルゴリズムを考える。
論文 参考訳（メタデータ） (2024-02-12T03:31:34Z) - High-dimensional Linear Bandits with Knapsacks [8.862707047517913]
特徴量が大きい高次元条件下で,knapsack (CBwK) 問題を用いた文脈的帯域幅について検討した。
本研究では,スパース推定をオンラインで行うハードしきい値アルゴリズムのオンライン版を開発する。
この統合されたアプローチは、特徴次元に対数的に依存するサブリニアな後悔を達成できることを示す。
論文 参考訳（メタデータ） (2023-11-02T15:40:33Z) - 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) - 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) - Complexity Analysis of a Countable-armed Bandit Problem [9.163501953373068]
遊びの地平線上で期待される累積的後悔を最小限に抑えるという古典的問題を考察する。
我々は、$K=2$のとき、$mathcalOleft(log n right)$の率最適有限時間インスタンス依存後悔を実現するアルゴリズムを提案する。
問題に対する後悔の順序と複雑さは、古典的MAB問題と非常に類似していることを示しているが、アルゴリズム設計における性能境界の特性と健全な側面は、後者とはかなり異なる。
論文 参考訳（メタデータ） (2023-01-18T00:53:46Z) - 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) - Non-stationary Bandits with Knapsacks [6.2006721306998065]
非定常環境におけるクナプサック(BwK)による包帯問題について検討する。
我々は、この問題の上下境界を導出するために、非定常対策を両方採用する。
論文 参考訳（メタデータ） (2022-05-25T01:22:36Z) - 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) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Recurrent Submodular Welfare and Matroid Blocking Bandits [22.65352007353614]
最近の研究は、マルチアームバンディット問題(MAB)の研究に焦点をあてている。
我々は、任意のマトロイドに対して$ (1 - frac1e)$-approximation を得ることのできる新しいアルゴリズムのアイデアを開発した。
鍵となる要素は、相関的な(インターリーブされた)スケジューリング技術である。
論文 参考訳（メタデータ） (2021-01-30T21:51:47Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。