論文の概要: Near Optimal Memory-Regret Tradeoff for Online Learning

• arxiv url: http://arxiv.org/abs/2303.01673v1
• Date: Fri, 3 Mar 2023 02:24:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-06 16:29:37.362451
• Title: Near Optimal Memory-Regret Tradeoff for Online Learning
• Title（参考訳）: オンライン学習のための最適メモリ-レグレットトレードオフ
• Authors: Binghui Peng and Aviad Rubinstein
• Abstract要約: 約$sqrtn$Memoryは必要であり、また、$o(T)$ regretを取得するのに十分であることを示す。 また、エージェントが選択した過去の専門家を観察できる適応的な敵についても検討する。
• 参考スコア（独自算出の注目度）: 14.50671354550329
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the experts problem, on each of $T$ days, an agent needs to follow the advice of one of $n$ ``experts''. After each day, the loss associated with each expert's advice is revealed. A fundamental result in learning theory says that the agent can achieve vanishing regret, i.e. their cumulative loss is within $o(T)$ of the cumulative loss of the best-in-hindsight expert. Can the agent perform well without sufficient space to remember all the experts? We extend a nascent line of research on this question in two directions: $\bullet$ We give a new algorithm against the oblivious adversary, improving over the memory-regret tradeoff obtained by [PZ23], and nearly matching the lower bound of [SWXZ22]. $\bullet$ We also consider an adaptive adversary who can observe past experts chosen by the agent. In this setting we give both a new algorithm and a novel lower bound, proving that roughly $\sqrt{n}$ memory is both necessary and sufficient for obtaining $o(T)$ regret.
• Abstract（参考訳）: 専門家の問題では、$t$ の日ごとに、エージェントは$n$ ``experts'' のいずれかのアドバイスに従う必要がある。 毎日、各専門家のアドバイスにかかわる損失が明らかにされる。 学習理論の基本的な結果は、エージェントが消滅する後悔、すなわち、その累積損失は、最高の視界の専門家の累積損失の$o(T)$以内である。 エージェントは、すべての専門家を思い出すのに十分なスペースなしでうまく機能できるか? PZ23] で得られたメモリ-リグレットトレードオフを改善し,[SWXZ22] の下位境界にほぼ一致するように, 難解な敵に対する新しいアルゴリズムを与える。 $\bullet$ エージェントが選択した過去の専門家を観察できる適応的な敵も検討する。 この設定では、新しいアルゴリズムと新しい下限を与え、およそ$\sqrt{n}$メモリが必要であり、$o(t)$ regretを得るのに十分であることを示す。

関連論文リスト

• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  我々は,エージェント群を協調させようとする学習者の視点で,マルチエージェント模倣学習(MAIL)問題を研究する。 MAILの以前の作業のほとんどは、基本的には、デモのサポート内で専門家の振る舞いにマッチする問題を減らすものです。 エージェントが戦略的でないという仮定の下で、学習者と専門家の間の価値ギャップをゼロにするのに十分であるが、戦略的エージェントによる逸脱を保証するものではない。
  論文  参考訳（メタデータ） (2024-06-06T16:18:20Z)
• 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)
• Impact of Decentralized Learning on Player Utilities in Stackelberg Games [57.08270857260131]
  多くの2エージェントシステムでは、各エージェントは別々に学習し、2つのエージェントの報酬は完全に一致しない。 分散学習を用いたStackelbergゲームとしてこれらのシステムをモデル化し、標準後悔ベンチマークが少なくとも1人のプレイヤーにとって最悪の線形後悔をもたらすことを示す。 我々は,これらのベンチマークに関して,両プレイヤーにとってほぼ最適な$O(T2/3)を後悔するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-29T23:38:28Z)
• An Online Learning Theory of Brokerage [3.8059763597999012]
  オンライン学習の観点からトレーダー間のブローカーについて検討する。 既に研究されている他の二国間貿易問題とは異なり、指定された買い手や売り手の役割が存在しない場合に焦点を当てる。 第1の場合、最適率は$sqrtT$に低下し、第2の場合、問題は解けなくなる。
  論文  参考訳（メタデータ） (2023-10-18T17:01:32Z)
• Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
  オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。 学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
  論文  参考訳（メタデータ） (2023-10-08T07:04:22Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Achieving Better Regret against Strategic Adversaries [15.51709428653595]
  本研究では,学習者が相手の行動について余分な知識を持つオンライン学習問題について検討する。 我々は,正規化リーダ(AFTRL)とProd-Best Response(Prod-BR)の2つの新しいオンライン学習アルゴリズムを提案する。 AFTRLは、外部の後悔に対して$O(1)$、または$O(1)$、遠回りの後悔に対して$O(1)$を達成する。
  論文  参考訳（メタデータ） (2023-02-13T19:34:36Z)
• 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)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• Nonstochastic Bandits with Infinitely Many Experts [1.7188280334580197]
  無限に多くの専門家と非確率的盗賊の問題を考察する。 有限個の専門家に対して、正しい専門家ランキングの推測を可能にするExp4.Pの変種を提案する。 そして、この変種を無限に多くの専門家に作用するメタアルゴリズムに組み込む。
  論文  参考訳（メタデータ） (2021-02-09T22:42:36Z)
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret [115.85354306623368]
  本研究では,未知の遷移カーネルを持つマルコフ決定過程におけるリスク感応性強化学習について検討する。 確率的に効率的なモデルレスアルゴリズムとして、リスク感性価値反復(RSVI)とリスク感性Q-ラーニング(RSQ)を提案する。 RSVIが $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big) に達したことを証明しています。
  論文  参考訳（メタデータ） (2020-06-22T19:28:26Z)

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

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