論文の概要: Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamics
- arxiv url: http://arxiv.org/abs/2302.13653v1
- Date: Mon, 27 Feb 2023 10:47:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-28 15:55:22.826946
- Title: Equilibrium Bandits: Learning Optimal Equilibria of Unknown Dynamics
- Title（参考訳）: 平衡バンド:未知力学の最適平衡を学習する
- Authors: Siddharth Chandak, Ilai Bistritz, Nicholas Bambos
- Abstract要約: 未知のシステムを制御するために、$K$アクションのうちの1つを選ぶことができる意思決定者を考えてみましょう。
システムのダイナミクスは意思決定者にとって未知であり、各ターンの最後にノイズの多い報酬しか観測できない。
既存のバンディットアルゴリズムは、逆数でも、この問題に対して線形な(タウ)後悔を達成する。
均衡に達するまで待つ価値がなければ、素早くアクションを切り替えることを知っている新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 23.722837647516357
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Consider a decision-maker that can pick one out of $K$ actions to control an
unknown system, for $T$ turns. The actions are interpreted as different
configurations or policies. Holding the same action fixed, the system
asymptotically converges to a unique equilibrium, as a function of this action.
The dynamics of the system are unknown to the decision-maker, which can only
observe a noisy reward at the end of every turn. The decision-maker wants to
maximize its accumulated reward over the $T$ turns. Learning what equilibria
are better results in higher rewards, but waiting for the system to converge to
equilibrium costs valuable time. Existing bandit algorithms, either stochastic
or adversarial, achieve linear (trivial) regret for this problem. We present a
novel algorithm, termed Upper Equilibrium Concentration Bound (UECB), that
knows to switch an action quickly if it is not worth it to wait until the
equilibrium is reached. This is enabled by employing convergence bounds to
determine how far the system is from equilibrium. We prove that UECB achieves a
regret of $\mathcal{O}(\log(T)+\tau_c\log(\tau_c)+\tau_c\log\log(T))$ for this
equilibrium bandit problem where $\tau_c$ is the worst case approximate
convergence time to equilibrium. We then show that both epidemic control and
game control are special cases of equilibrium bandits, where $\tau_c\log
\tau_c$ typically dominates the regret. We then test UECB numerically for both
of these applications.
- Abstract（参考訳）: 未知のシステムを制御するために$k$アクションの中から1つを$t$ターンで選択できる意思決定者を考える。
アクションは異なる設定やポリシーとして解釈される。
同じ作用を固定すると、システムは漸近的にこの作用の関数として一意の平衡に収束する。
システムのダイナミクスは意思決定者にとって未知であり、各ターンの最後にノイズの多い報酬しか観測できない。
その意思決定者は、その累積報酬をT$ターンで最大化したい。
平衡がよいものを学ぶことは、より高い報酬をもたらすが、システムが平衡に収束するのを待つことは貴重な時間である。
既存のバンディットアルゴリズムは確率的あるいは逆数的であり、この問題に対して線形な(自明な)後悔をもたらす。
我々は、平衡に達するまで待つ価値がなければ素早く作用を切り替えることを知っている、上平衡濃度境界 (UECB) と呼ばれる新しいアルゴリズムを提案する。
これは収束境界を用いて系が平衡からどれくらい離れているかを決定することで実現される。
我々は、この平衡帯域問題に対して、UECBが$\mathcal{O}(\log(T)+\tau_c\log(\tau_c)+\tau_c\log(T))$の後悔を達成することを証明している。
すると、流行制御とゲーム制御の両方が平衡バンディットの特別な場合であり、そこでは通常、$\tau_c\log \tau_c$が後悔を支配する。
次に、これら両方のアプリケーションでuecbを数値的にテストします。
関連論文リスト
- Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Games played by Exponential Weights Algorithms [0.0]
各プレイヤーは、初期混合動作と固定学習率を特徴とする指数重み付けアルゴリズムを使用する。
厳密なナッシュ均衡が存在するときは常に、次の段階で厳密なナッシュ均衡を行う確率は、ほぼ確実に0または1に収束することを示す。
論文 参考訳（メタデータ） (2024-07-09T08:49:51Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。
Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。
また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
論文 参考訳（メタデータ） (2024-03-13T01:51:30Z) - A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning [53.83345471268163]
非定常マルチエージェントシステムにおける平衡の学習について検討する。
単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
論文 参考訳（メタデータ） (2023-06-12T23:48:24Z) - Local Convergence of Gradient Methods for Min-Max Games: Partial
Curvature Generically Suffices [0.5439020425819]
2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡の収束について検討する。
偏曲のおかげで、円錐粒子法 -- 重みを最適化し、混合戦略をサポートする -- は、固定支持法よりも一般的に収束する。
論文 参考訳（メタデータ） (2023-05-26T21:43:56Z) - Bayes correlated equilibria and no-regret dynamics [9.89901717499058]
本稿では,不完全情報を持つゲームの基本モデルであるベイズゲームに対する平衡概念について検討する。
我々は,各プレイヤーのプライベート情報を収集し,関連するレコメンデーションをプレイヤーに送信する仲介者によって実現可能なコミュニケーション均衡に焦点を当てる。
本稿では,非直交スワップ後悔を線形上界で最小化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-11T06:22:51Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳（メタデータ） (2022-10-24T09:32:40Z) - Safe Equilibrium [1.7132914341329848]
標準的なゲーム理論解の概念であるナッシュ均衡は、すべてのプレイヤーが合理的に振る舞うことを仮定する。
我々は,特定の確率で合理的に行動する相手をモデル化する,セーフ均衡と呼ばれる新しい解の概念を提案する。
我々は、全ての戦略形式ゲームに安全な平衡が存在することを証明し、その計算がPPADハードであることを証明する。
論文 参考訳（メタデータ） (2022-01-12T01:45:51Z) - Multi-Leader Congestion Games with an Adversary [0.5914780964919123]
本研究では,複数のユーザ(リーダ)がリソースセットから1つのリソースを選択するマルチリーダシングルフォロワ・コングリゲーションゲームについて検討する。
純粋なナッシュ平衡は存在せず、従って近似平衡を考える。
与えられたインスタンスのすべての$alpha$-approximate equilibriaの中で、最小の$alpha$で、最適な近似平衡を効率的に計算する方法を示す。
論文 参考訳（メタデータ） (2021-12-14T14:47:43Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。