Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization

• URL: http://arxiv.org/abs/2402.11835v1
• Date: Mon, 19 Feb 2024 04:58:39 GMT
• Title: Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization
• Authors: Luca D'Amico-Wong, Hugh Zhang, Marc Lanctot, David C. Parkes
• Abstract summary: We propose ABCs, a best-of-both-worlds algorithm combining Boltzmann Q-learning (BQL) and counterfactual regret minimization (CFR) ABCs adaptively chooses what fraction of the environment to explore by measuring the stationarity of the environment's reward and transition dynamics. In Markov decision processes, ABCs converges to the optimal policy with at most an O(A) factor slowdown compared to BQL, where A is the number of actions in the environment.
• Score: 25.25031447644468
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose ABCs (Adaptive Branching through Child stationarity), a best-of-both-worlds algorithm combining Boltzmann Q-learning (BQL), a classic reinforcement learning algorithm for single-agent domains, and counterfactual regret minimization (CFR), a central algorithm for learning in multi-agent domains. ABCs adaptively chooses what fraction of the environment to explore each iteration by measuring the stationarity of the environment's reward and transition dynamics. In Markov decision processes, ABCs converges to the optimal policy with at most an O(A) factor slowdown compared to BQL, where A is the number of actions in the environment. In two-player zero-sum games, ABCs is guaranteed to converge to a Nash equilibrium (assuming access to a perfect oracle for detecting stationarity), while BQL has no such guarantees. Empirically, ABCs demonstrates strong performance when benchmarked across environments drawn from the OpenSpiel game library and OpenAI Gym and exceeds all prior methods in environments which are neither fully stationary nor fully nonstationary.

Related papers

• RLAS-BIABC: A Reinforcement Learning-Based Answer Selection Using the BERT Model Boosted by an Improved ABC Algorithm [6.82469220191368]
  Answer selection (AS) is a critical subtask of the open-domain question answering (QA) problem. The present paper proposes a method called RLAS-BIABC for AS, which is established on attention mechanism-based long short-term memory (LSTM) and the bidirectional encoder representations from transformers (BERT) word embedding.
  arXiv  Detail & Related papers  (2023-01-07T08:33:05Z)
• Solving Continuous Control via Q-learning [54.05120662838286]
  We show that a simple modification of deep Q-learning largely alleviates issues with actor-critic methods. By combining bang-bang action discretization with value decomposition, framing single-agent control as cooperative multi-agent reinforcement learning (MARL), this simple critic-only approach matches performance of state-of-the-art continuous actor-critic methods.
  arXiv  Detail & Related papers  (2022-10-22T22:55:50Z)
• Actor-Critic based Improper Reinforcement Learning [61.430513757337486]
  We consider an improper reinforcement learning setting where a learner is given $M$ base controllers for an unknown Markov decision process. We propose two algorithms: (1) a Policy Gradient-based approach; and (2) an algorithm that can switch between a simple Actor-Critic scheme and a Natural Actor-Critic scheme.
  arXiv  Detail & Related papers  (2022-07-19T05:55:02Z)
• The Complexity of Markov Equilibrium in Stochastic Games [44.77547027158141]
  We show that computing approximate stationary Markov coarse correlated equilibria (CCE) in general-sum games is computationally intractable. Our results stand in sharp contrast to normal-form games where exact CCEs are efficiently computable.
  arXiv  Detail & Related papers  (2022-04-08T10:51:01Z)
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games [3.441021278275805]
  Learning in games is arguably the most standard and fundamental setting in multi-agent reinforcement learning (MARL) We establish the finite-sample complexity of fully decentralized Q-learning algorithms in a significant class of general approximation games (SGs) We focus on the practical while challenging setting of fully decentralized MARL, where neither the rewards nor the actions of other agents can be observed by each agent.
  arXiv  Detail & Related papers  (2021-12-15T03:33:39Z)
• Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees [43.10380224532313]
  We study the emergence of coordinated behavior by autonomous agents using an actor-critic (AC) algorithm. We propose and analyze a class of coordinated actor-critic algorithms (CAC) in which individually parametrized policies have a it shared part and a it personalized part. This work provides the first finite-sample guarantee for decentralized AC algorithm with partially personalized policies.
  arXiv  Detail & Related papers  (2021-10-11T20:26:16Z)
• Predict then Interpolate: A Simple Algorithm to Learn Stable Classifiers [59.06169363181417]
  Predict then Interpolate (PI) is an algorithm for learning correlations that are stable across environments. We prove that by interpolating the distributions of the correct predictions and the wrong predictions, we can uncover an oracle distribution where the unstable correlation vanishes.
  arXiv  Detail & Related papers  (2021-05-26T15:37:48Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Single-partition adaptive Q-learning [0.0]
  Single- Partition adaptive Q-learning (SPAQL) is an algorithm for model-free episodic reinforcement learning. Tests on episodes with a large number of time steps show that SPAQL has no problems scaling, unlike adaptive Q-learning (AQL) We claim that SPAQL may have a higher sample efficiency than AQL, thus being a relevant contribution to the field of efficient model-free RL methods.
  arXiv  Detail & Related papers  (2020-07-14T00:03:25Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  We present SUNRISE, a simple unified ensemble method, which is compatible with various off-policy deep reinforcement learning algorithms. SUNRISE integrates two key ingredients: (a) ensemble-based weighted Bellman backups, which re-weight target Q-values based on uncertainty estimates from a Q-ensemble, and (b) an inference method that selects actions using the highest upper-confidence bounds for efficient exploration.
  arXiv  Detail & Related papers  (2020-07-09T17:08:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.