論文の概要: Blackwell's Approachability with Approximation Algorithms

• arxiv url: http://arxiv.org/abs/2502.03919v1
• Date: Thu, 06 Feb 2025 09:54:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-07 14:31:20.771053
• Title: Blackwell's Approachability with Approximation Algorithms
• Title（参考訳）: 近似アルゴリズムによるブラックウェルのアプローチ可能性
• Authors: Dan Garber, Mhna Massalha,
• Abstract要約: プレイヤーと相手のベクター値の繰り返しゲームを考える。 プレイヤーのセットのみに近似アルゴリズムが組み込まれている場合、よりシンプルで効率的なアルゴリズムが提供される。
• 参考スコア（独自算出の注目度）: 15.266876140036052
• License:
• Abstract: We revisit Blackwell's celebrated approachability problem which considers a repeated vector-valued game between a player and an adversary. Motivated by settings in which the action set of the player or adversary (or both) is difficult to optimize over, for instance when it corresponds to the set of all possible solutions to some NP-Hard optimization problem, we ask what can the player guarantee \textit{efficiently}, when only having access to these sets via approximation algorithms with ratios $\alpha_{\mX} \geq 1$ and $ 1 \geq \alpha_{\mY} > 0$, respectively. Assuming the player has monotone preferences, in the sense that he does not prefer a vector-valued loss $\ell_1$ over $\ell_2$ if $\ell_2 \leq \ell_1$, we establish that given a Blackwell instance with an approachable target set $S$, the downward closure of the appropriately-scaled set $\alpha_{\mX}\alpha_{\mY}^{-1}S$ is \textit{efficiently} approachable with optimal rate. In case only the player's or adversary's set is equipped with an approximation algorithm, we give simpler and more efficient algorithms.
• Abstract（参考訳）: 我々は,プレイヤーと相手の繰り返しベクトル値のゲームを考えるブラックウェルの卓越したアプローチ可能性問題を再考する。 例えば、NP-Hard最適化問題に対する全ての可能な解の集合に対応する場合、プレイヤーは、それぞれ$\alpha_{\mX} \geq 1$ と $ 1 \geq \alpha_{\mY} > 0$ の比率を持つ近似アルゴリズムを通してのみこれらの集合にアクセスできることを保証できるかを問う。 プレイヤーが単調な好みを持つならば、ベクター値の損失$\ell_1$ over $\ell_2$ if $\ell_2 \leq \ell_1$ を好まないという意味で、適切なスケールのセット $\alpha_{\mX}\alpha_{\mY}^{-1} S$ が最適レートでアプローチ可能なブラックウェルのインスタンスを与えられたときに、適切なスケールのセット $S$ を下方閉鎖することを確立する。 プレイヤーのセットのみに近似アルゴリズムが組み込まれている場合、よりシンプルで効率的なアルゴリズムが提供される。

関連論文リスト

• Corrupted Learning Dynamics in Games [62.73758165845971]
  すべてのプレイヤーが楽観的な追従型リーダー(OFTRL)に従うと、平衡は$O(log T)$の速さで計算できる。 本稿では,各プレイヤーが所定のアルゴリズムによって提案される戦略から逸脱する程度に依存する速度で,適応的に平衡を求める学習ダイナミクスを提案する。
  論文  参考訳（メタデータ） (2024-12-10T02:23:44Z)
• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-11-18T23:55:59Z)
• Chasing Convex Bodies and Functions with Black-Box Advice [7.895232155155041]
  ブラックボックスアドバイスによる凸関数追跡の問題点を考察する。 オンラインの意思決定者は、$textitConsistency$.com($textitConsistency$.com)と呼ばれる、うまく機能するときにアドバイスに匹敵するコストを求める。 本稿では,この問題の凸性を利用して,この制限を回避できる2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-23T15:30:55Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)
• Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits [20.207989166682832]
  2つの一般的な線形バンディット設定におけるモデル選択の問題について考察する。 まず、[K]$におけるarm $iの平均的な報酬は、$mu_i+ langle alpha_i,t,theta*|$である。 我々は、ALBが$O(|theta*|sqrtT)$の後悔のスケーリングを達成することを示す。
  論文  参考訳（メタデータ） (2020-06-04T02:19:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)

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

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