論文の概要: 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を数値的にテストします。
関連論文リスト
- A Black-box Approach for Non-stationary Multi-agent Reinforcement
Learning [41.608459163192684]
非定常マルチエージェントシステムにおける平衡の学習について検討する。
単エージェント学習へのブラックボックス還元による様々な平衡の検証方法を示す。
論文 参考訳(メタデータ) (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) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳(メタデータ) (2022-08-22T17:24:55Z) - 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) - Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
一般的なゲームでStackelberg平衡を効率的に学習する方法は、サンプルから非常にオープンなままです。
本稿では,2プレーヤターンベース汎用ゲームにおけるStackelberg平衡のサンプル効率学習に関する理論的研究を開始する。
論文 参考訳(メタデータ) (2021-02-23T05:11:07Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳(メタデータ) (2020-02-17T17:04:16Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳(メタデータ) (2020-01-27T03:44:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。