論文の概要: On Interpolating Experts and Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2307.07264v2
- Date: Fri, 4 Aug 2023 05:07:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-07 15:21:04.175065
- Title: On Interpolating Experts and Multi-Armed Bandits
- Title（参考訳）: 補間専門家とマルチアーマッドバンドについて
- Authors: Houshuang Chen, Yuchen He, Chihao Zhang
- Abstract要約: 我々は、$mathbfm$-MABに対して厳密なミニマックス後悔境界を証明し、その純粋な探索バージョンである$mathbfm$-BAIに対して最適なPACアルゴリズムを設計する。
その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
- 参考スコア（独自算出の注目度）: 1.9497955504539408
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning with expert advice and multi-armed bandit are two classic online
decision problems which differ on how the information is observed in each round
of the game. We study a family of problems interpolating the two. For a vector
$\mathbf{m}=(m_1,\dots,m_K)\in \mathbb{N}^K$, an instance of $\mathbf{m}$-MAB
indicates that the arms are partitioned into $K$ groups and the $i$-th group
contains $m_i$ arms. Once an arm is pulled, the losses of all arms in the same
group are observed. We prove tight minimax regret bounds for $\mathbf{m}$-MAB
and design an optimal PAC algorithm for its pure exploration version,
$\mathbf{m}$-BAI, where the goal is to identify the arm with minimum loss with
as few rounds as possible. We show that the minimax regret of $\mathbf{m}$-MAB
is $\Theta\left(\sqrt{T\sum_{k=1}^K\log (m_k+1)}\right)$ and the minimum number
of pulls for an $(\epsilon,0.05)$-PAC algorithm of $\mathbf{m}$-BAI is
$\Theta\left(\frac{1}{\epsilon^2}\cdot \sum_{k=1}^K\log (m_k+1)\right)$. Both
our upper bounds and lower bounds for $\mathbf{m}$-MAB can be extended to a
more general setting, namely the bandit with graph feedback, in terms of the
clique cover and related graph parameters. As consequences, we obtained tight
minimax regret bounds for several families of feedback graphs.
- Abstract（参考訳）: 専門家のアドバイスとマルチアームの盗賊による学習は、ゲームの各ラウンドでどのように情報が観察されるかが異なる2つの古典的なオンライン決定問題である。
我々はその2つを補間する問題の家系を研究する。
ベクトル $\mathbf{m}=(m_1,\dots,m_K)\in \mathbb{N}^K$ に対して、$\mathbf{m}$-MAB の例は、腕が$K$グループに分割され、$i$-th 群は$m_i$アームを含むことを示す。
一度腕を引っ張ると、同じグループのすべての腕の損失が観察される。
我々は、$\mathbf{m}$-MABに対して厳密なミニマックス後悔境界を証明し、純粋な探索バージョンである$\mathbf{m}$-BAIに対して最適なPACアルゴリズムを設計する。
我々は、$\mathbf{m}$-mabのミニマックスの後悔は$\theta\left(\sqrt{t\sum_{k=1}^k\log (m_k+1)}\right)であり、$(\epsilon,0.05)$-pacアルゴリズムの最小プル数は$\theta\left(\frac{1}{\epsilon^2}\cdot \sum_{k=1}^k\log (m_k+1)\right)であることを示した。
上限と下限はいずれも、クランクカバーと関連するグラフパラメータの観点から、より一般的な設定、すなわち、グラフフィードバックを伴うバンディットに拡張できます。
その結果、フィードバックグラフのいくつかのファミリに対して、厳密なミニマックス後悔境界を得た。
関連論文リスト
- Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Blocked Collaborative Bandits: Online Collaborative Filtering with
Per-Item Budget Constraints [46.65419724935037]
本稿では,複数のユーザを抱えるエンブロック型協調バンドイットの問題点について考察する。
私たちのゴールは、時間とともにすべてのユーザーが獲得した累積報酬を最大化するアルゴリズムを設計することです。
textttB-LATTICEは、予算制約の下で、ユーザ毎に$widetildeO(sqrtmathsfT(sqrtmathsfM-1)$を後悔する。
論文 参考訳（メタデータ） (2023-10-31T11:04:21Z) - 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) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Approximate Top-$m$ Arm Identification with Heterogeneous Reward
Variances [11.555138461092177]
この問題の最悪のサンプルの複雑さは$Thetaleft(sum_i = 1n fracsigma_i2epsilon2 lnfrac1delta + sum_i in Gm fracsigma_j2epsilon2 textEnt(sigma2_Gr) right)$$$$$Gm, Gl, Grである。
論文 参考訳（メタデータ） (2022-04-11T16:41:33Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Understanding Bandits with Graph Feedback [0.0]
一般的な後悔すべき上界$Oleft(left(delta*log |V|right)frac13Tfrac23right)$と下界$Omegaleft(left(delta*/alpharight)frac13Tfrac23right)$を証明します。
いくつかのグラフの特別な族に対して、$left(log |V|right)frac13$ factorを排除できることを示す。
論文 参考訳（メタデータ） (2021-05-29T09:35:28Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - 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) - A Closer Look at Small-loss Bounds for Bandits with Graph Feedback [39.78074016649885]
グラフフィードバックを用いた対向多腕バンディットの低損失境界について検討する。
一般の強可観測グラフに対する最初の小さな空間境界を導出する。
また、弱可観測グラフに対する小空間境界を導出する最初の試みも行う。
論文 参考訳（メタデータ） (2020-02-02T03:48:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。