論文の概要: Stochastic Bandits with Vector Losses: Minimizing $\ell^\infty$-Norm of
Relative Losses
- arxiv url: http://arxiv.org/abs/2010.08061v1
- Date: Thu, 15 Oct 2020 23:03:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 03:25:31.116983
- Title: Stochastic Bandits with Vector Losses: Minimizing $\ell^\infty$-Norm of
Relative Losses
- Title（参考訳）: ベクトル損失をもつ確率帯域:相対損失の$\ell^\infty$-Norm最小化
- Authors: Xuedong Shang, Han Shao, Jian Qian
- Abstract要約: マルチアームバンディットは、クリック率の最大化を目標とするレコメンデーションシステムに広く適用されている。
本稿では、この状況を複数の損失を伴って、$K$の武器付きバンディットの問題としてモデル化する。
- 参考スコア（独自算出の注目度）: 21.085722900446257
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-armed bandits are widely applied in scenarios like recommender systems,
for which the goal is to maximize the click rate. However, more factors should
be considered, e.g., user stickiness, user growth rate, user experience
assessment, etc. In this paper, we model this situation as a problem of
$K$-armed bandit with multiple losses. We define relative loss vector of an arm
where the $i$-th entry compares the arm and the optimal arm with respect to the
$i$-th loss. We study two goals: (a) finding the arm with the minimum
$\ell^\infty$-norm of relative losses with a given confidence level (which
refers to fixed-confidence best-arm identification); (b) minimizing the
$\ell^\infty$-norm of cumulative relative losses (which refers to regret
minimization). For goal (a), we derive a problem-dependent sample complexity
lower bound and discuss how to achieve matching algorithms. For goal (b), we
provide a regret lower bound of $\Omega(T^{2/3})$ and provide a matching
algorithm.
- Abstract（参考訳）: マルチアームバンディットは、クリック率の最大化を目標とするレコメンダシステムのようなシナリオで広く採用されている。
しかし、ユーザー持久率、ユーザー成長率、ユーザー体験評価など、より多くの要因が考慮されるべきである。
本稿では,この状況を,複数の損失を伴うk$-armed banditの問題としてモデル化する。
我々は、$i$-th のエントリが$i$-th の損失に対して、arm と最適なarm を比較したarm の相対的損失ベクトルを定義する。
私たちは2つの目標を学びました
(a)所定の信頼度(固定信頼度ベストアーム識別)による相対損失の最小$\ell^\infty$-normの腕を求めること。
(b)累積相対損失の$\ell^\infty$ノルムの最小化(後悔の最小化)。
ゴールのために
(a)問題依存のサンプル複雑性を低域で導出し,マッチングアルゴリズムの達成方法について議論する。
ゴールのために
(b)残念なことに$\omega(t^{2/3})$という下限を提供し、マッチングアルゴリズムを提供する。
関連論文リスト
- Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。
我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。
両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
論文 参考訳（メタデータ） (2023-12-27T09:32:18Z) - 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) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Double Doubly Robust Thompson Sampling for Generalized Linear Contextual
Bandits [8.508198765617198]
一般化線形報酬に$tildeO(sqrtkappa-1 phi T)$ regret over $T$ roundsを提案する。
また、確率的マージン条件下では、$O(kappa-1 phi log (NT) log T)$ regret bound for $N$ arms も提供する。
論文 参考訳（メタデータ） (2022-09-15T00:20:38Z) - Risk-averse Contextual Multi-armed Bandit Problem with Linear Payoffs [7.125769932993104]
リスク・逆条件下での線形ペイオフに対するコンテキスト多重武装バンディット問題について考察する。
各ラウンドにおいて、各アームのコンテキストが明らかにされ、意思決定者は1つのアームを選択して、対応する報酬を受け取ります。
解離モデルに対してトンプソンサンプリングアルゴリズムを適用し,提案アルゴリズムの変種に対する包括的後悔解析を行う。
論文 参考訳（メタデータ） (2022-06-24T18:48:35Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Scale Free Adversarial Multi Armed Bandits [13.757095663704858]
本稿では,MAB(Scale-Free Adversarial Multi Armed Bandit)問題について考察する。
我々はFTRLアルゴリズムを設計するが、これはMABに対する最初の無スケールな後悔の保証が伴う。
また,Bregman Divergencesの局所ノルム下界を求める新しい手法を開発した。
論文 参考訳（メタデータ） (2021-06-08T21:26:57Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - An Optimal Elimination Algorithm for Learning a Best Arm [37.18327505953403]
古典的な問題である$(epsilon,delta)$-PAC学習をベストアームとみなす。
本稿では,$(epsilon,delta)$-PAC学習を最適なアームとして提案する。
論文 参考訳（メタデータ） (2020-06-20T20:21:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。