Source-linked AI summary
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments
Sriram Srinivasan, Marc Lanctot, Vinicius Zambaldi, Julien Perolat, Karl Tuyls, Remi Munos, Michael Bowling
TL;DR
The paper addresses model-free policy optimization for partially observable multiagent games, where agents learn from experience without modeling opponents or the environment. It relates actor-critic updates to regret minimization, analyzes their convergence, and evaluates them in Poker domains, where they reach approximate Nash equilibria at rates similar to or better than baseline model-free methods.
Problem
Multiagent reinforcement learning in partially observable adversarial environments lacks well-understood policy-gradient and actor-critic guarantees, particularly in model-free settings.
Method
The paper proposes actor-critic policy updates connected to regret minimization and applies them with reinforcement-learning function approximation in model-free zero-sum games.
Results
Actor-critic variants converge empirically to approximate Nash equilibria in benchmark Poker domains at rates similar to or better than baseline model-free algorithms, while some outperform baselines against fixed bots.
Takeaways & Limitations
Actor-critic methods provide model-free, online alternatives connected to regret minimization and can perform competitively in partially observable Poker environments.
Takeaways & Limitations
The variants are not guaranteed to have regret sublinear in K and therefore may not converge to a Nash equilibrium.
Abstract
from arXiv · showhide
Optimization of parameterized policies for reinforcement learning (RL) is an important and challenging problem in artificial intelligence. Among the most common approaches are algorithms based on gradient ascent of a score function representing discounted return. In this paper, we examine the role of these policy gradient and actor-critic algorithms in partially-observable multiagent environments. We show several candidate policy update rules and relate them to a foundation of regret minimization and multiagent learning techniques for the one-shot and tabular cases, leading to previously unknown convergence guarantees. We apply our method to model-free multiagent reinforcement learning in adversarial sequential decision problems (zero-sum imperfect information games), using RL-style function approximation. We evaluate on commonly used benchmark Poker domains, showing performance against fixed policies and empirical convergence to approximate Nash equilibria in self-play with rates similar to or better than a baseline model-free algorithm for zero sum games, without any domain-specific state space reductions.
1 Introduction
Multiagent policy optimization is difficult under non-stationarity and partial observability, especially when agents learn without environment models or domain-specific abstractions. The paper studies model-free actor-critic updates for adversarial partially observable games and connects them to regret minimization.
- Deep reinforcement learning has achieved strong results across games, 3D environments, robotics, and other sequential decision-making domains.
- Simultaneous learning makes each agent’s environment non-stationary and can invalidate the Markov assumptions of standard reinforcement-learning methods.
- Partial observability challenges traditional reinforcement-learning techniques, while computer poker provides a common benchmark for such multiagent settings.
- Existing poker approaches such as Libratus and DeepStack rely on Poker-specific knowledge and are not model-free, requiring a perfect environment model for look-ahead search.
- The paper proposes actor-critic policy updates inspired by their connection to regret minimization and analyzes their convergence properties in model-free adversarial games.
2 Background and Related Work
The paper situates actor-critic policy optimization within partially observable multiagent reinforcement learning, policy gradients, and regret-minimization methods for imperfect-information games. It contrasts CFR-style sampling and classical MARL approaches with on-policy actor-critic methods that address sampling variance and state generalization.
- Policy optimization: Policy gradient methods directly update differentiable parameterized policies, while actor-critic methods additionally learn a parameterized critic estimating policy value.This contrasts with value-based methods that estimate state or action values and derive epsilon-greedy policies.
- Multiagent reinforcement learning: Partially observable multiagent reinforcement learning gives each agent observation histories and individual rewards, making learning difficult even in cooperative settings.In zero-sum games, equilibrium and regret-minimization concepts provide the main solution framework.
- Regret minimization: CFR accumulates counterfactual regrets and derives new policies through regret-matching or exponentially weighted experts.Its estimates are based on counterfactual values associated with information states and actions.
- Regret minimization: MCCFR samples trajectories with an exploratory behavior policy and uses importance sampling to obtain unbiased regret and value estimates.Model-free outcome sampling enables online regret minimization without requiring the player’s updates to depend on opponents’ policies or the transition model.
- Actor-critic connection: CFR and MCCFR face sampling variance from reach-probability corrections and lack generalization across states without abstractions or a perfect model.The paper presents actor-critics as on-policy MCCFR that address both problems.
- Related work: Classical MARL policy-gradient studies found cyclical dynamics and were largely limited to one-shot games, while newer methods improve scalability but independent learning can miss optimal stochastic policies or overfit.The paper’s methods do not model opponents and instead adapt mainly from current experience through their on-policy nature.
3 Multiagent Actor-Critics: Advantages and Regrets
The paper interprets actor-critic advantages as scaled counterfactual regrets and develops regret-based policy updates for partially observable multiagent learning. It analyzes convergence under tabular projected updates while noting that the proposed variants are not generally guaranteed to achieve sublinear regret.
- Advantages and Regrets: CFR updates policies using thresholded cumulative counterfactual regret, motivating regret policy gradient and regret matching policy gradient variants.RPG minimizes an upper bound on thresholded cumulative regret, while RMPG weights policy gradients by thresholded regret.
- Learning Dynamics: In Matching Pennies, regret dynamics resemble replicator dynamics, and average policies converged to equilibrium across the games examined.The paper also notes that computing average policies can be costly with function approximation because past data may need to be stored.
- Advantages and Regrets: Actor-critic advantages can be interpreted as immediate counterfactual regrets scaled by the inverse opponents’ reach probability.This connects standard actor-critic quantities to regret minimization in partially observable games.
- Partially Observable Games: Monte Carlo policy-gradient estimates remain valid without the Markov property when temporal-difference bootstrapping is not used, including under partial observability and multiple agents.The analysis distinguishes these estimates from counterfactual values, which can differ substantially when a state is rarely reached.
- Convergence Analysis: Projected policy-gradient and actor-critic iterations receive tabular two-player zero-sum convergence guarantees under specified learning rates and simplex projection.The same type of guarantee is also stated for strong policy-gradient and strong actor-critic variants.
- Limitations: None of the proposed variants is guaranteed to have regret sublinear in K, so convergence to a Nash equilibrium is not assured in general.This limitation is stated explicitly despite the tabular projected convergence results.
4 Empirical Evaluation
The empirical evaluation tests neural actor-critic methods in Kuhn and Leduc poker, comparing them with NFSP and A2C through equilibrium convergence and performance against fixed bots.
- Experimental Setup: The experiments evaluate actor-critic algorithms on Kuhn poker and Leduc poker using neural-network policies and critics.The implementation uses two fully connected layers of 128 units, followed by value or softmax outputs.
- Evaluation Metrics: NASHCONV measures convergence toward approximate Nash equilibria, while fixed-bot evaluation measures expected reward against CFR500.CFR500 represents the average policy after 500 CFR iterations.
- Training Setup: Training uses repeated policy-evaluation updates followed by policy improvement, with separate optimizers and annealed policy-improvement learning rates.The policy-improvement learning rate is annealed to zero over 20M steps.
- Convergence to Equilibrium: In two-player Leduc, actor-critic variants are comparable long-term, although NFSP converges faster initially and all actor-critics outperform A2C.RMPG appears to plateau during convergence.
- Performance Against Fixed Bots: QPG and RPG score higher than A2C against fixed CFR bots and eventually outperform NFSP.Performance is averaged across player seats.
5 Conclusion
The conclusion presents model-free actor-critic updates as connected to regret minimization and reports competitive empirical behavior in benchmark Poker domains. It also identifies formal guarantees for sampled methods and extensions to continuing, cooperative, and potential games as future work.
- Contributions: The paper discusses actor-critic update rules for multiagent reinforcement learning and connects them to counterfactual regret minimization.The algorithms are model-free and online, so they do not require explicit models of opponents or the environment.
- Empirical Findings: Actor-critic algorithms converge empirically to approximate Nash equilibria in benchmark Poker domains at rates similar to or better than model-free zero-sum baselines.Some variants also perform better than NFSP’s average policy against fixed bots.
- Empirical Findings: RPG and QPG appear to outperform RMPG in the reported experiments.This comparison is specific to the evaluated actor-critic variants and experiments.
- Future Work: Future work includes formal probabilistic guarantees for sample-based on-policy Monte Carlo CFR and extension to continuing tasks.The authors also identify cooperative and potential games as possible settings for further convergence analysis.
Appendices
The appendices relate reinforcement learning terminology and policy iteration to counterfactual regret minimization, describe sampling and actor-critic variants, and state assumptions about partial observability and episode length.
- Notation and CFR: CFR is framed as policy iteration: value evaluation is followed by regret-based policy improvement.Regret matching assigns action probabilities proportional to thresholded cumulative regret, while average-policy convergence follows the Folk theorem.
- Sampling and Convergence: Monte Carlo CFR replaces full trajectory sweeps with sampled trajectories and estimated values, with probabilistic convergence bounds under sampling.The appendix describes sampled values as unbiased estimates in the cited formulation.
- Partial Observability: Temporal-difference bootstrapping is generally unavailable because information states in partially observable multiagent environments do not satisfy the Markov property.An optimal policy at one state can depend on policies at other information states.
- Notation and Terminology: The appendix distinguishes POMDP belief states from information states because belief states include an associated distribution over histories.It also provides a cross-field mapping of analogous terminology.
- Actor-Critic Variants: The RPG variant differs from A2C by using gradient descent with ∇RPG θ and an action-value critic instead of a state-value baseline.The pseudocode is given in Algorithm 2.
- Episode Assumptions: The analysis focuses on bounded-length episodes with tmax exceeding the maximum episode length, avoiding TD-style bootstrapping from other values.Longer episodes may require sequence truncation.
D Analysis of Regret Dynamics in Matrix Games
The analysis connects actor-critic policy updates to regret-minimization dynamics in matrix games and examines their behavior in matching pennies, RPS, bias RPS, and generalized RPS. Average RPG dynamics converge to mixed Nash equilibria in the studied games, while projected actor-critic and policy-gradient updates admit local regret guarantees.
- Matrix-game dynamics: RPG dynamics cycle around mixed Nash equilibria, but their time averages converge to those equilibria in matching pennies, RPS, and bias RPS.The same pattern holds in generalized RPS: replicator and RPG trajectories cycle, whereas their average-time dynamics converge.
- Policy-update interpretation: Actor-critic policy improvement can be formulated as a local online convex optimization problem, with one GIGA(s) instance solving the problem at each information state.The adversary for each local problem is the opponent policy outside that state.
- Policy-update interpretation: ACPI is similar to CFR, but replaces regret matching with GIGA(s); PGPI is treated as a special case of the same argument.This establishes a direct connection between policy-gradient-style updates and regret-minimization procedures.
- Regret guarantees: Projected ACPI and projected PGPI with learning rate k^-1/2 are equivalent to running GIGA(s), yielding a bounded total local regret after K steps.The equivalence follows after rewriting the updates in terms of policy gradients; constant shifts do not change simplex projections.
- Regret guarantees: Because total local regret is sublinear in K, average regret at each information state approaches 0 as K tends to infinity.The result concerns local regret for the sequence of policies played at each state.
E.2 Proof of Theorem 2
Theorem 2 analyzes a stronger ACPI update that ascends state-local values simultaneously rather than weighting changes only by their reach probability. Its proof obtains a local-regret result, but coefficient scaling prevents a direct reduction to counterfactual regret.
- Update objective: Standard ACPI weights state updates by reach probability because it optimizes the initial-state value, making its steps resemble conservative policy improvement.Strong ACPI instead modifies the policy toward locally maximizing q(s,a) at every state.
- Update objective: Strong ACPI uses state-local gradients and a modified value definition to improve every state-local objective simultaneously.The resulting value is presented as more desirable than the reach-weighted value used earlier.
- Regret analysis: The coefficients 1/B_-i(π^k,s) scale regret magnitudes, so negative regrets may receive larger weights than positive regrets in the worst case.Consequently, the proof cannot remove these coefficients to obtain a sum over only counterfactual regrets.
F On the similarity of QPG and RPG
The paper shows that RPG and QPG gradients are closely related: at each state, the RPG gradient is proportional to the QPG gradient. This similarity may help explain their similar empirical behavior.
- Gradient relationship: The RPG gradient is proportional to the QPG gradient at any state, with the proportionality involving the number of actions having positive advantage.The derivation uses the fact that the derivative of the positive-part operator is zero for negative inputs.
- Empirical interpretation: The authors suggest that this gradient similarity could partly explain the similar behavior of QPG and RPG in experiments.This is presented as a possible explanation rather than a proven causal account.
G Additional details on the experiments
The experiments compare implementation choices for policy-gradient methods and relate the proposed actor-critic framework to existing regret-dynamics algorithms. Actor-critic methods also support behavioral policies and standard RL-style function approximation.
- Hyperparameters: SGD outperformed Adam, and learning-rate sweeps selected 0.01 for the policy-gradient experiments.The reported best entropy cost was 0.1 across the domains.
- Hyperparameters: The best critic-update and batch-size settings were Nq = 128 and batch size = 4 across the games.These values were selected from sweeps over the specified grids.
- Relation to prior algorithms: The reduction of ACPI to CFR is analogous to the reduction from sequence-form replicator dynamics to CFR.This situates the proposed connection within prior regret-dynamics reductions.
- Relation to prior algorithms: With sampled gradients, the algorithm becomes analogous to on-policy Monte Carlo sampling in reinforcement learning.This connects the matrix-game analysis to model-free trajectory-based estimation.
- Function approximation: Actor-critic algorithms operate directly on behavioral state-action tables and can incorporate RL-style function approximation to generalize over states.This contrasts with sequence-form Q-learning, which samples a deterministic policy at each step.
I Negative Results: Monte Carlo Regression CFR (Retracted Baseline)
Monte Carlo RCFR was introduced as a model-free, sampled alternative to RCFR, but the authors could not obtain stable results with Monte Carlo sampling. Its implementation combines sampled trajectories, learned critics, replay data, and policy prediction, with Adam outperforming SGD in their RCFR experiments.
- Negative result: The authors were unable to obtain stable results with Monte Carlo sampling and identified further investigation of the instability as necessary.This prevented Monte Carlo RCFR from serving as a reliable comparison baseline.
- RCFR comparison: RCFR approximates cumulative regrets for all information states with a regressor, then derives policies through regret matching.The implementation used raw inputs and neural networks; Adam performed better than SGD, which was unstable for this problem.
- Monte Carlo RCFR: Monte Carlo RCFR was proposed as a model-free version of RCFR that samples trajectories instead of sweeping the full state space.Unlike RCFR, it is independent of the environment and other players’ policies.
- RCFR comparison: Regression CFR was unsuitable as an experimental baseline because it requires full tree passes and free access to the environment.The supplied figure compares instantaneous and average cumulative regret targets, with reservoir sampling reported as important for immediate-regret targets.
- Monte Carlo RCFR: The method trains a value critic from samples and stores one million experience tuples using reservoir sampling.Stored tuples include the information state, return, sampled immediate regret, and chosen action; reservoir sampling preserves a uniform sample in expectation.
- Monte Carlo RCFR: Monte Carlo RCFR samples exploratory trajectories and predicts an average policy from stored actions to assess exploitability.Exploration begins fully uniform and decays toward the current policy, while the predicted average policy is trained by classification.
J Corrections to the Original Paper
The authors corrected the original theoretical statements by restoring omitted O(K) terms and questioning whether weighted-regret guarantees imply unweighted-regret guarantees. They could not establish how frequently the resulting worst-case sequences occur in practice.
- Correction: The original statements of Theorems 1 and 2 omitted O(K) terms because weighted-regret bounds were treated as implying unweighted-regret bounds.The authors identify the lack of guarantees on how negative and positive regrets are weighted as the central problem.
- Correction: The authors investigated stronger GIGA guarantees and self-play with decaying learning rates, but sought rather than established a bound on absolute regret sums.The attempted fix targeted subsequences containing only negative or only positive regret.
- Open question: The frequency of the worst-case sequences remains unknown, making empirical analysis a proposed direction for future work.The authors explicitly state that they are unaware how often these sequences occur in practice.