論文の概要: Minimax Regret for Cascading Bandits

• arxiv url: http://arxiv.org/abs/2203.12577v1
• Date: Wed, 23 Mar 2022 17:37:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-24 13:45:15.866365
• Title: Minimax Regret for Cascading Bandits
• Title（参考訳）: カスケードバンドのためのミニマックスレグレット
• Authors: Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, R. Srikant
• Abstract要約: Cascadingは、学習タスクをモデル化し、部分的なフィードバックのラウンドで$n$のアイテムから$L$のアイテムをランク付けする。 最もよく知られた下界と上界は、それぞれ$Omega(sqrtnL)$と$tildeO(sqrtnLK)$である。 また、CascadeUCB1はOmega(sqrtnLK)のサブ最適化に苦しむことも示しています。
• 参考スコア（独自算出の注目度）: 33.2023050753125
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cascading bandits model the task of learning to rank $K$ out of $L$ items over $n$ rounds of partial feedback. For this model, the minimax (i.e., gap-free) regret is poorly understood; in particular, the best known lower and upper bounds are $\Omega(\sqrt{nL/K})$ and $\tilde{O}(\sqrt{nLK})$, respectively. We improve the lower bound to $\Omega(\sqrt{nL})$ and show CascadeKL-UCB (which ranks items by their KL-UCB indices) attains it up to log terms. Surprisingly, we also show CascadeUCB1 (which ranks via UCB1) can suffer suboptimal $\Omega(\sqrt{nLK})$ regret. This sharply contrasts with standard $L$-armed bandits, where the corresponding algorithms both achieve the minimax regret $\sqrt{nL}$ (up to log terms), and the main advantage of KL-UCB is only to improve constants in the gap-dependent bounds. In essence, this contrast occurs because Pinsker's inequality is tight for hard problems in the $L$-armed case but loose (by a factor of $K$) in the cascading case.
• Abstract（参考訳）: cascading banditsは、部分的なフィードバックのラウンドで、$l$アイテムから$k$をランク付けする学習のタスクをモデル化する。 このモデルでは、ミニマックス(すなわち、ギャップのない)後悔は、よく知られた下限と上限はそれぞれ$\Omega(\sqrt{nL/K})$と$\tilde{O}(\sqrt{nLK})$である。 低域を$\Omega(\sqrt{nL})$に改善し、CascadeKL-UCB(KL-UCB指数で項目をランク付けする)がログ項に到達したことを示す。 驚いたことに、CascadeUCB1(UCB1を介してランク付けされている)は、サブ最適$\Omega(\sqrt{nLK})を後悔する可能性がある。 これは標準の$L$武装バンディットとは対照的であり、対応するアルゴリズムはどちらもminimax regret $\sqrt{nL}$(ログ項まで)を達成し、KL-UCBの主な利点はギャップ依存境界における定数を改善することである。 本質的には、ピンスカーの不等式は、l$-armed の場合では難しい問題に対して厳密であるが、cascading の場合では(k$ で)ゆるいためである。

関連論文リスト

• Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
  本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。 ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
  論文  参考訳（メタデータ） (2024-04-02T12:15:37Z)
• Minimax Optimal Submodular Optimization with Bandit Feedback [13.805872311596739]
  単調な部分モジュラー集合関数 $f: 2[n] rightarrow [0,1]$ をバンドイットフィードバックの下で最大化する。 具体的には、$f$は学習者には知られていないが、各時点で$t=1,dots,T$は、$|S_t| leq k$でセットの$S_tサブセット[n]$を選択し、$eta_t$が平均ゼロのサブガウスノイズである場合に、$f(S_t) + eta_t$を受け取る。
  論文  参考訳（メタデータ） (2023-10-27T20:19:03Z)
• On Interpolating Experts and Multi-Armed Bandits [1.9497955504539408]
  我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。 その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
  論文  参考訳（メタデータ） (2023-07-14T10:38:30Z)
• Tight Memory-Regret Lower Bounds for Streaming Bandits [11.537938617281736]
  学習者は オンラインの腕と サブリニアの腕の記憶を扱うことで 後悔を最小化することを目的としています 我々は,任意のアルゴリズムに対して,Omega left((TB)alpha K1-alpharight), α = 2B / (2B+1-1)$という,厳密な最悪ケースの残差を低く設定する。 また、一定のアームメモリを用いて、左(TB)アルファK1-αright)$の後悔の上限を達成できるマルチパスアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2023-06-13T16:54:13Z)
• Implicit bias of SGD in $L_{2}$-regularized linear DNNs: One-way jumps from high to low rank [22.850359181621023]
  行列補完のようなタスクでは、トレーニングデータに適合する最小限のランクで局所最小値に収束することが目標である。 SGDでは、常に上位から下位にジャンプする確率があるが、後退する確率はゼロである。
  論文  参考訳（メタデータ） (2023-05-25T13:17:32Z)
• An Experimental Design Approach for Regret Minimization in Logistic Bandits [26.674062544226636]
  ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。 そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-04T21:56:40Z)
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap [84.66885506098724]
  本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。 AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。 また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
  論文  参考訳（メタデータ） (2021-02-09T07:46:34Z)
• Adversarial Dueling Bandits [85.14061196945599]
  本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。 学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。 我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
  論文  参考訳（メタデータ） (2020-10-27T19:09:08Z)
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
  UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。 さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
  論文  参考訳（メタデータ） (2020-10-01T17:57:47Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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