論文の概要: Learning to Play Multi-Follower Bayesian Stackelberg Games
- arxiv url: http://arxiv.org/abs/2510.01387v1
- Date: Wed, 01 Oct 2025 19:20:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-03 16:59:20.837595
- Title: Learning to Play Multi-Follower Bayesian Stackelberg Games
- Title（参考訳）: マルチスローのベイジアン・スタックルバーグゲームを学ぶ
- Authors: Gerson Personnat, Tao Lin, Safwan Hossain, David C. Parkes,
- Abstract要約: マルチフォローのStackelbergゲームでは、リーダーは$L$アクションに対して混合戦略を実行し、$nge 1$フォロワー、それぞれが$K$のプライベートタイプを持つ。
リーダーが$T$ラウンドと$n$フォロワーと、未知のディストリビューションからサンプリングされたタイプと相互作用する。
リーダーの目標は、最適戦略の累積効力と実際に選択された戦略との差として定義される後悔を最小限にすることである。
- 参考スコア（独自算出の注目度）: 22.434143000543813
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a multi-follower Bayesian Stackelberg game, a leader plays a mixed strategy over $L$ actions to which $n\ge 1$ followers, each having one of $K$ possible private types, best respond. The leader's optimal strategy depends on the distribution of the followers' private types. We study an online learning version of this problem: a leader interacts for $T$ rounds with $n$ followers with types sampled from an unknown distribution every round. The leader's goal is to minimize regret, defined as the difference between the cumulative utility of the optimal strategy and that of the actually chosen strategies. We design learning algorithms for the leader under different feedback settings. Under type feedback, where the leader observes the followers' types after each round, we design algorithms that achieve $\mathcal O\big(\sqrt{\min\{L\log(nKA T), nK \} \cdot T} \big)$ regret for independent type distributions and $\mathcal O\big(\sqrt{\min\{L\log(nKA T), K^n \} \cdot T} \big)$ regret for general type distributions. Interestingly, those bounds do not grow with $n$ at a polynomial rate. Under action feedback, where the leader only observes the followers' actions, we design algorithms with $\mathcal O( \min\{\sqrt{ n^L K^L A^{2L} L T \log T}, K^n\sqrt{ T } \log T \} )$ regret. We also provide a lower bound of $\Omega(\sqrt{\min\{L, nK\}T})$, almost matching the type-feedback upper bounds.
- Abstract（参考訳）: マルチフォローのBayesian Stackelbergゲームでは、リーダーが$L$アクションに対して混合戦略を実行し、そこでは$n\ge 1$フォロワーがそれぞれ$K$のプライベートタイプを持つ。
リーダーの最適な戦略は、フォロワーのプライベートなタイプの分布に依存する。
リーダーが$T$ラウンドと$n$フォロワーと、未知のディストリビューションからサンプリングされたタイプと相互作用する。
リーダーの目標は、最適戦略の累積効力と実際に選択された戦略との差として定義される後悔を最小限にすることである。
異なるフィードバック設定の下で、リーダーのための学習アルゴリズムを設計する。
タイプフィードバックでは、各ラウンドの後にフォロワーの型を観測するアルゴリズムを設計し、独立型の分布に対して$\mathcal O\big(\sqrt{\min\{L\log(nKA T), nK \} \cdot T} \big)、一般型の分布に対して$\mathcal O\big(\sqrt{\min\{L\log(nKA T), K^n \} \cdot T} \big)を得る。
興味深いことに、これらの境界は多項式レートで$n$で成長しない。
アクションフィードバックでは、リーダーはフォロワーの行動のみを観察し、$\mathcal O( \min\{\sqrt{ n^L K^L A^{2L} L T \log T}, K^n\sqrt{ T } \log T \} )でアルゴリズムを設計する。
また、$\Omega(\sqrt{\min\{L, nK\}T})$という下界も提供します。
関連論文リスト
- Enjoying Non-linearity in Multinomial Logistic Bandits [66.36004256710824]
我々は,学習者が環境と対話する一般化線形帯域幅の変種である多項ロジスティック帯域幅問題を考察する。
我々は、$kappa_*$の定義を多項集合に拡張し、問題の非線形性を活用する効率的なアルゴリズムを提案する。
我々のメソッドは、代入$ smashwidetildemathcalO(Kd sqrtT/kappa_*) $, $K$はアクションの数で、$kappa_*
論文 参考訳（メタデータ） (2025-07-07T08:18:25Z) - Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries [34.38978643261337]
本稿では,適応的相手に対する帯域フィードバックの下で,有向非巡回グラフ(DAG)における最短経路問題について検討する。
我々は,任意の適応的敵に対して高い確率で$tilde O(sqrt|E|Tlog |X|)$の最小限の最小残差を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-01T06:35:42Z) - Online Learning of Halfspaces with Massart Noise [47.71073318490341]
我々はMassartノイズの存在下でのオンライン学習の課題について検討する。
計算効率のよいアルゴリズムで, 誤り境界が$eta T + o(T)$であることを示す。
我々はMassartオンライン学習者を用いて、任意のラウンドでランダムなアクションを選択するよりも、少なくとも$(1-1/k) Delta T - o(T)$の報酬を得られる効率的なバンディットアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-05-21T17:31:10Z) - Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。
私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。
目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
論文 参考訳（メタデータ） (2023-08-14T08:52:24Z) - Best-of-Both-Worlds Algorithms for Partial Monitoring [34.37963000493442]
非退化したグローバル可観測ゲームでは、レジームの後悔は$O(k3 m2 log(k_Pi T) / Delta_min2)$で制限される。
我々のアルゴリズムは、フィードバックグラフを用いたオンライン学習の分野におけるアルゴリズムにインスパイアされた、フォロー・ザ・レギュラライズド・リーダー・フレームワークに基づいている。
論文 参考訳（メタデータ） (2022-07-29T08:40:05Z) - 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) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-13T16:35:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。