論文の概要: Optimal anytime regret with two experts

• arxiv url: http://arxiv.org/abs/2002.08994v2
• Date: Thu, 26 Aug 2021 21:19:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 07:25:10.976924
• Title: Optimal anytime regret with two experts
• Title（参考訳）: 2人の専門家に最適な後悔
• Authors: Nicholas J. A. Harvey, Christopher Liaw, Edwin Perkins, Sikander Randhawa
• Abstract要約: 我々は、いつでも後悔を最小限に抑えるために、最初のミニマックス最適アルゴリズムを設計する。 このアルゴリズムは、計算のアイデアを用いて解決した後悔問題の連続的な類似を考慮し、設計する。
• 参考スコア（独自算出の注目度）: 11.959180302329358
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the classical problem of prediction with expert advice. In the fixed-time setting, where the time horizon is known in advance, algorithms that achieve the optimal regret are known when there are two, three, or four experts or when the number of experts is large. Much less is known about the problem in the anytime setting, where the time horizon is not known in advance. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts. Even for the case of two experts, Luo and Schapire have left open the problem of determining the optimal algorithm. We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret is $\gamma \sqrt{t} / 2$ at all time steps $t$, where $\gamma$ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue of the regret problem, which is solved using ideas from stochastic calculus.
• Abstract（参考訳）: 我々は専門家の助言で予測の古典的な問題を考察する。 時間的地平線が予め知られている固定時間設定では、最適な後悔を達成するアルゴリズムは、専門家が2人、3人、または4人いる場合、あるいは専門家の数が多ければ知られている。 時間軸が事前に分かっていない時間設定では、この問題についてはあまり知られていない。 ミニマックスの最適アルゴリズムは、専門家の数に関係なく、常に知られていなかった。 2人の専門家の場合でも、LuoとSchapireは最適なアルゴリズムを決定するという問題を解き放った。 任意の時間設定で後悔を最小限に抑えるための最初のminimax最適アルゴリズムを設計。 2人の専門家のケースを考察し、最善の後悔がすべての時間において$\gamma \sqrt{t} / 2$であることを証明し、ここで$\gamma$は35年前にブラウン運動の基本特性を研究する際に生じた自然定数である。 このアルゴリズムは、確率計算のアイデアを用いて解決した後悔問題の連続的な類似を考慮し、設計する。

関連論文リスト

• On the price of exact truthfulness in incentive-compatible online learning with bandit feedback: A regret lower bound for WSU-UX [8.861995276194435]
  古典的な予測ゲームと専門的なアドバイスと二進的な結果の1つの見方では、それぞれの専門家は反対に選択された信念を維持している。 本稿では、この問題の戦略的なバリエーションとして、自己中心的な専門家(レコメンデーション・シーキング)が紹介されている。 損失列の明示的な構成により、アルゴリズムは最悪の場合$Omega(T2/3)$lowboundに苦しむことを示した。
  論文  参考訳（メタデータ） (2024-04-08T02:41:32Z)
• Time-Varying Gaussian Process Bandits with Unknown Prior [18.93478528448966]
  PE-GP-UCBは時変ベイズ最適化問題を解くことができる。 これは、観測された関数の値が以前のいくつかの値と一致しているという事実に依存している。
  論文  参考訳（メタデータ） (2024-02-02T18:52:16Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Optimal Tracking in Prediction with Expert Advice [0.0]
  専門家のアドバイス設定を用いて予測を検証し、専門家の集合が生み出す決定を組み合わせて意思決定を行うことを目的とする。 我々は、専門家のアドバイス設定による予測の下で、最小限の動的後悔を達成する。 我々のアルゴリズムは、このような普遍的に最適で適応的で真にオンラインの保証を、事前の知識なしで生成した最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2022-08-07T12:29:54Z)
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions [98.75618795470524]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-13T17:58:58Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
  論文  参考訳（メタデータ） (2022-04-21T01:22:18Z)
• Efficient and Optimal Fixed-Time Regret with Two Experts [5.650647159993238]
  専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。 T$のラウンドと$n$のエキスパートを持つ場合、古典的な乗法的重み更新法は、$T$が事前に知られているときに、少なくとも$sqrt(T/2)ln n$の後悔を被る。 専門家が$n$の数が小さい/固定された場合、より後悔する保証のあるアルゴリズムが存在する。
  論文  参考訳（メタデータ） (2022-03-15T01:07:09Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Excursion Search for Constrained Bayesian Optimization under a Limited Budget of Failures [62.41541049302712]
  本稿では,所定の予算の失敗の関数として探索において許容されるリスクの量を制御する制御理論に基づく新しい意思決定者を提案する。 本アルゴリズムは, 種々の最適化実験において, 故障予算をより効率的に利用し, 一般に, 最先端の手法よりも, 後悔度を低くする。
  論文  参考訳（メタデータ） (2020-05-15T09:54:09Z)

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

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