論文の概要: Online Learning with Vector Costs and Bandits with Knapsacks

• arxiv url: http://arxiv.org/abs/2010.07346v1
• Date: Wed, 14 Oct 2020 18:28:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 14:40:59.013212
• Title: Online Learning with Vector Costs and Bandits with Knapsacks
• Title（参考訳）: ベクターコストによるオンライン学習とKnapsackによるバンド
• Authors: Thomas Kesselheim and Sahil Singla
• Abstract要約: オンライン学習にベクターコスト(OLVCp)を導入し、各時間に1,ldots,T$の$tのステップで、未知のベクターコストを発生させるアクションを実行する必要がある。 オンラインアルゴリズムの目標は、コストベクトルの和の$ell_p$ノルムを最小化することである。
• 参考スコア（独自算出の注目度）: 8.340947016086739
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce online learning with vector costs (\OLVCp) where in each time step $t \in \{1,\ldots, T\}$, we need to play an action $i \in \{1,\ldots,n\}$ that incurs an unknown vector cost in $[0,1]^{d}$. The goal of the online algorithm is to minimize the $\ell_p$ norm of the sum of its cost vectors. This captures the classical online learning setting for $d=1$, and is interesting for general $d$ because of applications like online scheduling where we want to balance the load between different machines (dimensions). We study \OLVCp in both stochastic and adversarial arrival settings, and give a general procedure to reduce the problem from $d$ dimensions to a single dimension. This allows us to use classical online learning algorithms in both full and bandit feedback models to obtain (near) optimal results. In particular, we obtain a single algorithm (up to the choice of learning rate) that gives sublinear regret for stochastic arrivals and a tight $O(\min\{p, \log d\})$ competitive ratio for adversarial arrivals. The \OLVCp problem also occurs as a natural subproblem when trying to solve the popular Bandits with Knapsacks (\BwK) problem. This connection allows us to use our \OLVCp techniques to obtain (near) optimal results for \BwK in both stochastic and adversarial settings. In particular, we obtain a tight $O(\log d \cdot \log T)$ competitive ratio algorithm for adversarial \BwK, which improves over the $O(d \cdot \log T)$ competitive ratio algorithm of Immorlica et al. [FOCS'19].
• Abstract（参考訳）: ベクトルコストによるオンライン学習(\olvcp)を導入する。ステップ$t \in \{1,\ldots,t\}$では、未知ベクトルコストが$[0,1]^{d}$となるようなアクション$i \in \{1,\ldots,n\}$をプレイする必要がある。 オンラインアルゴリズムの目標は、コストベクトルの総和の$\ell_p$ノルムを最小化することである。 これは従来のオンライン学習設定を$d=1$でキャプチャし、さまざまなマシン(次元)間の負荷のバランスを取るオンラインスケジューリングのようなアプリケーションのために、一般的な$d$として興味深い。 確率的および敵対的な到着設定の両方で \olvcp を研究し、問題を$d$次元から1次元に減らすための一般的な手順を与える。 これにより、従来のオンライン学習アルゴリズムをフルフィードバックモデルとバンディットフィードバックモデルの両方で使用して、(ほぼ)最適な結果を得ることができます。 特に、確率的到着に対するサブ線形後悔を与える1つのアルゴリズム(学習速度の選択まで)と、敵対的到着に対する競合比の厳密な$O(\min\{p, \log d\})を得る。 OLVCp問題は、Knapsacks (\BwK) 問題で人気のBanditsを解く際にも自然のサブプロブレムとして発生する。 この接続により、我々のOLVCp技術を用いて、確率的および対角的両方の設定において、BwKの(ほぼ)最適結果を得ることができる。 特に、逆数 \BwK に対する厳密な$O(\log d \cdot \log T)$競争比アルゴリズムを求め、Immorlica et al の$O(d \cdot \log T)$競争比アルゴリズムを改良する。 [focs'19]

関連論文リスト

• Online Learning of Halfspaces with Massart Noise [47.71073318490341]
  我々はMassartノイズの存在下でのオンライン学習の課題について検討する。 計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。 我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-05-21T17:31:10Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
  本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-06-09T05:39:05Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Contextual Bandits with Side-Observations [10.248045133793287]
  ソーシャルネットワークを介して接続されたユーザの推薦アルゴリズムを設計するために,両腕にサイドオブザーブメントが存在する場合のコンテキスト帯について検討する。 既存の学習アルゴリズムの素直な応用は、$Oleft(Nlog Tright)$ regretとなり、そこでは$N$がユーザ数であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T19:34:50Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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