Fugu-MT 論文翻訳(概要): Improved Regret Bounds for Bandits with Expert Advice

論文の概要: Improved Regret Bounds for Bandits with Expert Advice

arxiv url: http://arxiv.org/abs/2406.16802v1
Date: Mon, 24 Jun 2024 17:14:31 GMT
ステータス: 処理完了
システム内更新日: 2024-06-25 13:55:51.380454
Title: Improved Regret Bounds for Bandits with Expert Advice
Title（参考訳）: エキスパートアドバイザによるバンドのレグレトバウンドの改善
Authors: Nicolò Cesa-Bianchi, Khaled Eldowa, Emmanuel Esposito, Julia Olkhovskaya,
Abstract要約: 我々は、最悪のケースの後悔に対して$sqrtK T ln(N/K)$の下位境界を証明し、そこでは$K$はアクションの数、$N>K$はエキスパートの数、$T$はタイムホライズである。これは、前述した同じ順序の上界と一致し、$sqrtK T (ln N) / (ln K)$の最良の下界を改善する。
参考スコア（独自算出の注目度）: 16.699381591572163
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this research note, we revisit the bandits with expert advice problem. Under a restricted feedback model, we prove a lower bound of order $\sqrt{K T \ln(N/K)}$ for the worst-case regret, where $K$ is the number of actions, $N>K$ the number of experts, and $T$ the time horizon. This matches a previously known upper bound of the same order and improves upon the best available lower bound of $\sqrt{K T (\ln N) / (\ln K)}$. For the standard feedback model, we prove a new instance-based upper bound that depends on the agreement between the experts and provides a logarithmic improvement compared to prior results.
Abstract（参考訳）: 本研究ノートでは,バンディットを専門家の助言で再考する。制限されたフィードバックモデルの下では、最悪のケースの後悔に対して$\sqrt{K T \ln(N/K)}$の下位境界を証明し、そこでは$K$はアクションの数、$N>K$はエキスパートの数、$T$はタイムホライゾンとなる。これは、既に知られている同じ順序の上界と一致し、$\sqrt{K T (\ln N) / (\ln K)}$の最良の下界を改善する。標準フィードバックモデルでは、専門家間の合意に依存する新しいインスタンスベースの上限を証明し、以前の結果と比較して対数的改善を提供する。

関連論文リスト

The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-05-16T12:11:09Z)
Near-optimal Per-Action Regret Bounds for Sleeping Bandits [8.261117235807607]
睡眠中の包帯に対して, 行動毎のほぼ最適な後悔境界を導出する。合計で$K$、最大で$A$の武器が各ラウンドで$T$以上の場合、最もよく知られている上限は$O(KsqrtTAlnK)$である。本研究は睡眠専門家のアドバイスで盗賊の設定まで拡張し,その過程でEXP4を一般化する。
論文参考訳（メタデータ） (2024-03-02T21:22:46Z)
Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文参考訳（メタデータ） (2023-02-07T02:22:31Z)
Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文参考訳（メタデータ） (2022-10-24T18:40:19Z)
Constant regret for sequence prediction with limited advice [0.0]
予測とm$ge$2の専門家の損失を観測するために,p = 2の専門家のみを1ラウンド毎に組み合わせた戦略を提供する。学習者が1ラウンドにつき1人の専門家のフィードバックのみを観察することを制約されている場合、最悪の場合の後悔は"スローレート"$Omega$($sqrt$KT)である。
論文参考訳（メタデータ） (2022-10-05T13:32:49Z)
Norm-Agnostic Linear Bandits [9.700635713828698]
本稿では,そのような知識を初めて必要としない新しいアルゴリズムを提案する。我々は、その遺言を解析する。一つは、変更アームセット設定用、もう一つは固定アームセット設定用である。我々の数値実験は、標準的なアルゴリズムが$|theta*|le S$が正しくない場合に、$S$の知識が破滅的に失敗する可能性があることを仮定している。
論文参考訳（メタデータ） (2022-05-03T00:55:42Z)
The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文参考訳（メタデータ） (2022-03-18T08:03:20Z)
An Experimental Design Approach for Regret Minimization in Logistic Bandits [26.674062544226636]
ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-02-04T21:56:40Z)
Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
無限に多くの専門家と非確率的盗賊の問題を考察する。有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
論文参考訳（メタデータ） (2021-02-09T22:42:36Z)
Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-17T22:32:19Z)
Bandits with Knapsacks beyond the Worst-Case [87.54497614804409]
最悪の場合の視点を超えた3つの結果を提示します。第一に、対数的、インスタンス依存的後悔率の完全な特徴を与える上限と下限を提供する。第二に、与えられたラウンドにおけるアルゴリズムの性能を追跡するBwKの「簡単な後悔」を考察し、数ラウンドを除いては小さくないことを示す。
論文参考訳（メタデータ） (2020-02-01T18:50:44Z)

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