論文の概要: Protocols for Verifying Smooth Strategies in Bandits and Games

• arxiv url: http://arxiv.org/abs/2507.10567v1
• Date: Tue, 08 Jul 2025 07:14:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-16 19:46:02.727314
• Title: Protocols for Verifying Smooth Strategies in Bandits and Games
• Title（参考訳）: バンド・ゲームにおけるスムース戦略の検証プロトコル
• Authors: Miranda Christ, Daniel Reichman, Jonathan Shafer,
• Abstract要約: マルチアームバンディットおよび正規形式ゲームにおける戦略の近似最適性を検証するためのプロトコルについて検討する。 各プレイヤーが利用可能なアクションの数は多いため、ユーティリティオラクルへのクエリの数がアクションの数でサブ線形となるプロトコルを模索する。 このような検証は、特定の行動に過剰な確率質量を課さない十分にスムーズな戦略に対して可能であることを証明している。
• 参考スコア（独自算出の注目度）: 3.2061312711364223
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study protocols for verifying approximate optimality of strategies in multi-armed bandits and normal-form games. As the number of actions available to each player is often large, we seek protocols where the number of queries to the utility oracle is sublinear in the number of actions. We prove that such verification is possible for sufficiently smooth strategies that do not put too much probability mass on any specific action. We provide protocols for verifying that a smooth policy for a multi-armed bandit is $\varepsilon$-optimal. Our verification protocols require provably fewer arm queries than learning. Furthermore, we establish a nearly-tight lower bound on the query complexity of verification in our settings. As an application, we show how to use verification for bandits to achieve verification in normal-form games. This gives a protocol for verifying whether a given strategy profile is an approximate strong smooth Nash equilibrium, with a query complexity that is sublinear in the number of actions.
• Abstract（参考訳）: マルチアームバンディットおよび正規形式ゲームにおける戦略の近似最適性を検証するためのプロトコルについて検討する。 各プレイヤーが利用可能なアクションの数は多いため、ユーティリティオラクルへのクエリの数がアクションの数でサブ線形となるプロトコルを模索する。 このような検証は、特定の行動に過剰な確率質量を課さない十分にスムーズな戦略に対して可能であることを証明している。 マルチアームバンディットのスムーズなポリシーが$\varepsilon$-optimalであることを検証するためのプロトコルを提供する。 我々の検証プロトコルは、学習よりも明らかに少ないアームクエリを必要とする。 さらに、我々の設定における検証のクエリの複雑さに対して、ほぼ28の低いバウンダリを確立します。 アプリケーションとして,通常形式のゲームにおいて,ビジットの検証手法を用いて検証を行う方法を示す。 これにより、与えられた戦略プロファイルが、アクションの数でサブ線形なクエリ複雑性を持つ、近似的に強い滑らかなナッシュ均衡であるかどうかを検証するためのプロトコルが提供される。

関連論文リスト

• One Sample is Enough to Make Conformal Prediction Robust [53.78604391939934]
  共形予測は, 1つのランダムな摂動入力に対して前方通過しても, ある程度の堅牢性が得られることを示す。 提案手法は,入力毎に多数のパス(例えば100回程度)を使用するSOTA法と比較して,平均セットサイズが小さいロバストな集合を返す。
  論文  参考訳（メタデータ） (2025-06-19T19:14:25Z)
• The Cost of Restaking vs. Proof-of-Stake [0.18416014644193066]
  リスク要件の観点から,再試行プロトコルとProof-of-Stakeプロトコルの効率を比較検討する。 このような再帰グラフをセキュアなPoSプロトコルに変換することは,常に可能であることを示す。
  論文  参考訳（メタデータ） (2025-05-30T10:22:55Z)
• Quantile Multi-Armed Bandits with 1-bit Feedback [40.22079522118723]
  リスク感度と通信制約の要素を含むベストアーム識別のバリエーションについて検討する。 本研究では,雑音の多い二分探索をサブルーチンとして利用し,学習者が1ビットフィードバックによって定量報酬を推定できるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-02-10T17:03:33Z)
• Game-Theoretically Secure Distributed Protocols for Fair Allocation in Coalitional Games [2.1779479916071067]
  我々は,Shapley値に近似して乗算誤差を小さくする連立ゲームに対して,ゲーム理論的にセキュアなプロトコルを検討する。 ゲーム理論上のマクシミン・セキュリティの概念は、たとえ他の全てのプレイヤーが敵に感受性があるとしても、正直なプレイヤーの報酬を保証するために提案されている。
  論文  参考訳（メタデータ） (2024-12-26T12:13:21Z)
• When Can Proxies Improve the Sample Complexity of Preference Learning? [63.660855773627524]
  我々は,代行報酬の最大化が必ずしも真の報酬を増やすとは限らない,報酬ハッキングの問題に対処する。 プロキシフィードバックに関する十分な条件を概説し、満足すれば、プロキシデータが基底真理ポリシーを学習する際のサンプルの複雑さを確実に改善できることを示す。
  論文  参考訳（メタデータ） (2024-12-21T04:07:17Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Replay For Safety [51.11953997546418]
  経験的なリプレイでは、過去の遷移はメモリバッファに格納され、学習中に再使用される。 適切なバイアスサンプリング方式を用いることで,エファンセーフなポリシーを実現できることを示す。
  論文  参考訳（メタデータ） (2021-12-08T11:10:57Z)
• Solving Multi-Arm Bandit Using a Few Bits of Communication [42.13277217013971]
  マルチアームバンディット問題(マルチアームバンディット問題、MAB)は、報酬を逐次観察することで、一連のアクションの中からベストを選択することを目的とした、アクティブな学習フレームワークである。 分散エージェントが収集した報酬の通信を最適化することで,コミュニケーション問題に対処する。 汎用的な報酬量子化アルゴリズムQuBanを構築し、任意の(非回帰的な)MABアルゴリズムの上に適用して、新しい通信効率の対物を形成する。
  論文  参考訳（メタデータ） (2021-11-11T06:23:16Z)
• Minimum Entanglement Protocols for Function Estimation [0.0]
  我々は、少なくとも$k$-partite tanglement を用いて最適なプロトコルが存在することの必要十分条件を証明した。 我々のプロトコルは時間依存制御をある程度必要としており、関連する時間依存プロトコルのクラスは、ジェネリック関数の最適スケーリングを達成できないことを示す。
  論文  参考訳（メタデータ） (2021-10-14T18:00:00Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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