論文の概要: Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret

• arxiv url: http://arxiv.org/abs/2202.10997v1
• Date: Tue, 22 Feb 2022 15:58:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-23 16:56:41.711066
• Title: Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret
• Title（参考訳）: Minimax Regret for partial monitoring: Infinite Outcomes and Rustichini's Regret
• Authors: Tor Lattimore
• Abstract要約: 一般化された情報比は、全ての有限動作部分監視ゲームにおいてミニマックス後悔を決定することを示す。 1/2,1]$の任意の$pに対して、$np$ラウンドに対するミニマックスがサブポリノミカル因子まで$np$であるような無限の部分的監視ゲームが存在する。
• 参考スコア（独自算出の注目度）: 28.93486346263364
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games provided that (a) the standard definition of regret is used but the latent space where the adversary plays is potentially infinite; or (b) the regret introduced by Rustichini (1999) is used and the latent space is finite. Our results are complemented by a number of examples. For any $p \in [1/2,1]$ there exists an infinite partial monitoring game for which the minimax regret over $n$ rounds is $n^p$ up to subpolynomial factors and there exist finite games for which the minimax Rustichini regret is $n^{4/7}$ up to subpolynomial factors.
• Abstract（参考訳）: 我々は、Lattimore andgyorgy (2020) の一般化情報比のバージョンが、与えられた全ての有限動作部分監視ゲームに対する漸近的ミニマックス後悔を決定することを示す。 (a)後悔の標準的な定義は用いられるが、敵の遊びが潜在的に無限である潜在空間、または (b)Rustichini (1999) によって導入された後悔は使われ、潜在空間は有限である。 私たちの結果はいくつかの例で補完されています。 任意の$p \in [1/2,1]$に対して、$n$のラウンドに対するミニマックスの後悔が$n^p$、サブポリノミカル要素まで$n^p$であり、ミニマックスのRustichiniの後悔が$n^{4/7}$である有限ゲームが存在する。

関連論文リスト

• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
  我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。 そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。 対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2022-09-09T17:31:46Z)
• Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
  政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。 我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。 我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
  論文  参考訳（メタデータ） (2022-04-24T03:10:27Z)
• Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game [9.933208900617174]
  我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。 NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。 モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-03-11T13:45:42Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponent [9.094186120476174]
  ゼロサムゲームのための後サンプリング強化学習(PSRL-ZSG) ゼロサムゲームのための後サンプリング強化学習(PSRL-ZSG)を提案する。
  論文  参考訳（メタデータ） (2021-09-08T02:05:40Z)
• Near-Optimal No-Regret Learning in General Games [31.293412884145066]
  マルチプレイヤー汎用ゲームにおいて,Optimistic Hedge が $rm poly(log T)$ regret を達成することを示す。 我々の境界の系は、最適化的ヘッジが一般ゲームにおいて$tildeOleft(frac 1Tright)$の速度で粗相関平衡に収束するということである。
  論文  参考訳（メタデータ） (2021-08-16T06:53:02Z)
• No Discounted-Regret Learning in Adversarial Bandits with Delays [40.670563413892154]
  アルゴリズムが「割引なし」の場合、予想される遊びの割引エルゴジック分布が粗相関平衡(CCE)の集合に収束することを示した。 ゼロサムゲームでは、Nash平衡のセットに収束する割引エルゴディック平均のプレイには、ディスカウントレグレットが十分ではないことを示します。
  論文  参考訳（メタデータ） (2021-03-08T05:15:31Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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