Decentralized Bandit Learning of Markov Perfect Equilibria

arXiv:2610.14333 · cs.LG, math.OC · Submitted 2026-10-09 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Decentralized Bandit Learning of Markov Perfect Equilibria".

Jane: The gist: The fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium under strong monotonicity and sufficiently small time steps.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we’re looking at this paper now, "Decentralized Bandit Learning of Markov Perfect Equilibria." It’s about how agents can learn optimal strategies in these complex, multi-agent games without knowing what everyone else is doing.

Jane: That sounds really complicated to put simply. What does "Markov perfect equilibrium" even mean for someone who isn't deep into game theory?

Tom: Well, think of it like this: these agents are learning how to make the best move based only on what they see—their current state, their own action, and the reward they just got. The goal is to find a stable point where everyone’s strategy works best given that everyone else is also playing optimally.

Lu: What's interesting here is that this method learns these policies and the continuation values at the same time, which avoids needing separate timescales for policy updates and value estimation, which I think simplifies the learning dynamics considerably.

Meng: From a deployment standpoint, I’m thinking about how this affects our running costs. If we can learn these equilibria through this decentralized bandit learning process instead of some centralized training, that could mean less overhead during operation.

Lalam: From my perspective, the paper suggests that under the right conditions—strong monotonicity of those reward gradients and small time steps—the fully decentralized procedure converges almost surely to a unique stationary Markov perfect equilibrium.

Jane: Almost surely is a big word for us. So, if this method works, does it mean we can guarantee we’ll actually find that best strategy, or is there still a risk of getting stuck somewhere suboptimal?

Tom: The paper says yes. It provides a convergence guarantee of O(n minus one/two) and states that the error in the policy and value estimates goes to zero at a rate proportional to the square root of time <ref:2610.14333#pg1>. That’s a concrete performance metric we can actually measure.

Lu: And they also extend this to episodic finite-horizon learning, which means it can handle tasks where you only have a limited number of rounds before the game ends, and it converges almost surely to the unique finite-horizon Markov perfect equilibrium.

Meng: That episodic extension is important because in real production environments, things often have fixed time limits or episodes that end on a schedule, so being able to handle that structure is practical.

Lalam: The convergence for the episodic case means you can reliably find the best strategy for a task with a known endpoint, as long as those regularity and strong monotonicity assumptions hold.

Jane: So, what are they suggesting we should do differently compared to older methods? Is this just a refinement of existing techniques or is it fundamentally new in how we approach these games?

Tom: The paper focuses on using simultaneous perturbation stochastic approximation to update the actions, which seems like a clever way to estimate those gradients even when you don't know all the underlying game dynamics.

Title and authors: Lu: They use a one-point estimate of each agent’s pseudo-gradient derived from a perturbed action, the realized reward, and an estimate of the discounted continuation value. This handles that vanishing stochastic approximation bias quite elegantly.

Meng: That sounds efficient because it doesn't require us to run multiple complex simulations just to figure out what the gradient should be; we get an estimate directly from a single trajectory.

Lalam: The convergence rate O(n minus one/two) is what really stands out here when compared to other work on learning dynamics in discounted Markov games, which is how they frame it in their analysis of Höfer and Soner <ref:2610.14333#pg1>.

Jane: So, if we take this for context, what does this mean for a system that has to make decisions in real-time where the environment changes constantly?

Tom: It means that even with continuous actions and unknown reward functions, as long as the underlying game has strong monotonicity of those negative running-reward gradients and our time steps are small enough, we can still achieve convergence to the optimal equilibrium.

Lu: The setup involves a joint state process X t greater than or equal to zero taking values in a finite set X, and then defining the Bellman operator based on that structure, which is how they formalize the objective function maximization <ref:2610.14333#pg3,values in a finite set X>.

Meng: The paper also mentions an application example involving a discounted dynamic service game inspired by a strategic queueing model where the net payment is defined as r i (x, a) equals p i a i minus c E(a i) squared <ref:2610.14333#pg1>. That gives us a real-world scenario to test the theory against.

Lalam: They show that for this specific application, agents update their centered actions u i equals a i minus alpha c in U I equals

-varrho,varrho: , which is a standard bounded action space setup for these types of problems.

Jane: That connection to queueing models makes it feel more grounded than just abstract math. It shows how this could apply to resource allocation or service decisions in dynamic settings.

Tom: The complexity analysis shows that for every state x in X, the expected number of states visited E

s n(X n): is at least zeta squared ES n minus K n minus three p over four. That gives us a bound on the exploration aspect of the learning process.

Lu: They also have conditions on perturbations and learning rates, like delta n approaching zero and lambda epsilon approaching zero, which are crucial for ensuring that the approximation holds in practice.

Meng: Those explicit conditions on our learning rates are what I’m really interested in from a production standpoint; if we don't meet those small step size requirements, the convergence breaks down immediately.

Lalam: And there’s also a condition on exploration, requiring that there is some zeta greater than zero such that the probability of seeing some state y given the current state x and action a is at least zeta.

Title and authors: Jane: So to summarize this paper, we have a decentralized method for learning Markov perfect equilibria in continuous-action games using simultaneous perturbation stochastic approximation and it guarantees convergence under strong monotonicity and small time steps.

Tom: And they even provided an extension to episodic finite-horizon learning with a corresponding convergence guarantee of O(n minus one/two) <ref:2610.14333#pg1,extension to episodic finite-horizon learning>.

Lu: The main implication is that we can learn complex, multi-agent strategies purely from private bandit feedback, without needing to know the objectives of the other agents.

Meng: It means we can deploy AI systems in environments where they interact with other agents but only see their own outcomes, which is a huge win for practical implementation.

Lalam: This paper is about how to learn ordinary Markov perfect equilibria in continuous-action games from private bandit feedback alone, and it gives us a solid framework to pursue that goal.

Jane: So the next thing we have to think about is what these results mean for how we design AI agents for real-world decision making.

Tom: Yeah, and I’m curious if there are any specific scenarios where this O(n minus one/two) rate might not hold, or if the strong monotonicity condition is too restrictive in some practical setups <ref:2610.14333#pg1>.

Lu: The authors did extend the analysis to state-dependent action spaces, which means it can handle situations where an agent's available actions actually depend on the current state itself, which is a bit more realistic than just having a fixed action set.

Meng: Handling those state-dependent spaces would be interesting because many real systems have constraints that change based on the situation unfolding.

Lalam: The paper also mentions their natural extension to episodic finite-horizon learning, which is what we talked about earlier, showing it's not just a theoretical construct but has a practical application path.

Jane: Okay, so we’ve covered the mechanics and the guarantees of this decentralized bandit learning of Markov perfect equilibria. It sounds like a solid foundation for building agents that can learn robust policies in complex interactions.

Tom: Exactly. We'll keep an eye on how the community builds on this, especially regarding those adaptive learning rates you mentioned earlier, which I think would be the next big area for research.

Lu: And I think focusing on those dynamic settings is where the real challenge lies, moving from these theoretical guarantees to practical deployment under more volatile conditions.

Meng: From my side, the cost of running these models efficiently will dictate how much we can actually scale this up in a production environment.

Lalam: The paper gives us a clear path on how to learn these equilibria using just the information each agent has, which is really valuable for understanding distributed AI systems.

Jane: It’s been interesting to see how they connect this deep theoretical work back to concrete application examples like service games. We've got a lot of interesting things coming down the pipeline.

The paper's summary: Jane: So, to recap, this paper is about how different AI agents can learn their best strategies in a multi-agent game just by looking at their own experiences and rewards without needing to talk to everyone else.

Tom: Right. They’re using something called decentralized bandit learning and they’re aiming for this thing called the Markov perfect equilibrium, which is basically the best stable outcome for all agents playing optimally together.

Lu: What makes this interesting is that they show you how to update the policies and the value estimates at the same time, which simplifies things because you don't have to juggle two different learning speeds.

Meng: From a deployment standpoint, if an AI system is interacting with other agents in a real-time environment, being able to learn these equilibrium points without needing perfect communication channels sounds like it could save on coordination overhead.

Lalam: The core idea they’re pushing is that under the right conditions—strong monotonicity of those reward gradients and very small time steps—the decentralized procedure actually converges almost surely to this unique stationary Markov perfect equilibrium.

Jane: Almost surely again, Tom, can we break down what that means for a listener who isn't deep in stochastic processes? What does "almost surely" actually guarantee us here?

Tom: It guarantees that if you run this learning process long enough, without any weird random luck messing things up too much, the algorithm will settle down into that one perfect equilibrium. It’s not just a possibility; it’s a mathematical certainty under those specific assumptions.

Lu: And they quantify that certainty with a convergence rate of big O of n minus one-half for both the policy and value estimates, which is pretty good for learning dynamics in these continuous action spaces.

Meng: An n minus one-half rate means that as you gather more data or time steps, the error shrinks predictably at a square root speed. That’s a concrete performance metric we can actually track when we try to deploy this.

Jane: So, if I were listening for something that could change how an AI agent makes decisions in a dynamic system—like managing traffic flow or resource allocation—what does this convergence guarantee tell me about the reliability of that learning?

Tom: It tells you that the learning process is robust. As long as those regularity assumptions hold, you don't just get some random policy; you get the specific stationary point where everyone is playing their best given what they observe.

Lu: And they also extend this to episodic finite-horizon learning, which means if your task has a clear end date, say a certain number of rounds, it converges almost surely to the unique finite-horizon Markov perfect equilibrium.

Jane: That’s a big extension. So, we can use this not just for infinite tasks that go on forever in theory but also for practical scenarios with defined stopping points.

Meng: Practical scenarios are where I get nervous about convergence; what happens when the environment changes unexpectedly mid-episode? The paper doesn't explicitly detail how it handles sudden, massive shifts in the game dynamics.

Lalam: They do state that they rely on small time steps to ensure that the approximation holds, which is their main lever for keeping things stable during those transitions.

Tom: And they also have conditions on exploration, requiring some minimum probability of seeing certain states or actions so the agent doesn't just get stuck in a local optimum forever.

Jane: So we’ve seen the mechanics and the guarantees, but what does this all mean for how we actually build these decentralized AI agents for real-world decision making?

Lu: It gives us a solid framework to learn optimal policies from private feedback alone, which is huge because in many industrial settings, you can't always share everything with every other agent.

Tom: Exactly. It means the performance of the system becomes less dependent on perfect centralized coordination and more dependent on how well the individual agents can learn their own local best moves.

Jane: So we’ve covered the mechanics and the guarantees of this decentralized bandit learning of Markov perfect equilibria, showing it converges under strong monotonicity for infinite tasks and episodic tasks with an O of n minus one-half rate. Now we need to think about what this actually means for how we design AI agents for real-world decision making.

The paper's improvements: Tom: So we’re looking at how they improve the original decentralized bandit learning setup for Markov perfect equilibria on this paper now. It’s about adding some specific mechanisms to make it more robust and faster.

Jane: What are they changing in terms of the process? Is this just tweaking the learning rates, or is there a whole new way they’re estimating those gradients?

Lu: They are using simultaneous perturbation stochastic approximation, but they're extending that by allowing agent-dependent clocks and step sizes, which is motivated by previous work on dynamic settings.

Meng: Agent-dependent clocks sound complicated to implement at scale; what does that actually mean for the computational load when you’re running this on a production server?

Tom: It means agents can operate on different timescales; some might need to update their strategy much faster than others, which lets them adapt quicker in dynamic environments.

Jane: That sounds like it could be really useful if one part of the system needs to react instantly while another part can afford a slower update cycle.

Lalam: They’re also refining how they estimate the necessary pseudo-gradient using a one-point estimate derived from a perturbed action, the realized reward, and an estimate of the discounted continuation value.

Tom: That handles that problem where you don't know all the continuation values perfectly; it gives us a stable single point to work with, which cuts down on that vanishing stochastic-approximation bias.

Lu: And they show how this setup leads to a one-point estimate of each agent’s pseudo-gradient, which is much more efficient than trying to solve the whole system simultaneously.

Jane: So it’s making the gradient estimation cleaner and more stable by using just one trajectory instead of running a whole simulation for every update.

Meng: That efficiency is good; if we can get better estimates with less compute time, that helps us keep the cost of running this learning process down when we deploy it.

Tom: And they have moved toward an O of n minus one-half convergence rate, which is a concrete number for how fast the error goes to zero over time.

Lu: That square root speed means we can predict exactly how long it will take for our AI agents to reach that stable equilibrium point.

Jane: So, the improvement here is giving us both a better way to estimate what the agent *should* do and a clearer picture of how fast they’ll get there.

Tom: And they also showed that this can be extended to state-dependent action spaces, which means it handles situations where an agent's available actions actually depend on the current state itself.

Meng: That’s more realistic because in many physical systems, the constraints on what you can do change depending on what’s happening right now.

Jane: So this method isn't just for simple games with fixed action sets; it can handle those more complex, state-dependent scenarios where the rules of engagement are constantly shifting.

Lalam: And they also reinforced the episodic learning side, showing that it still converges almost surely to that finite-horizon Markov perfect equilibrium when the episode has a clear end date.

Tom: So we’ve got convergence guarantees for infinite tasks, speed-up mechanisms for adaptation, better gradient estimation, and handling state-dependent actions.

Lu: The main implication is that this framework is much more versatile than the original formulation; it covers a wider range of game dynamics while still maintaining strong theoretical backing.

Conclusion: Tom: So we’re wrapping up this look at "Decentralized Bandit Learning of Markov Perfect Equilibria." This paper is about how agents learn their best strategies in a multi-agent game just by looking at their own experiences and rewards without needing to talk to everyone else.

Jane: It’s been fascinating because they show us a way to find those stable points where all agents are playing optimally together, even when they don't know what the other players are thinking.

Lu: The paper’s biggest contribution is providing a solid theoretical framework that works for both infinite-horizon games and finite-horizon episodic tasks, which is pretty versatile.

Meng: From a deployment view, having something that converges almost surely to a Markov perfect equilibrium under these conditions means we can deploy AI systems in complex environments with less need for perfect centralized coordination.

Lalam: I’m really confident in this result because the convergence guarantees are tied to strong monotonicity of those reward gradients and small time steps, which are standard requirements for stability.

Tom: Yeah, and they give us that O of n minus one-half rate on the policy and value estimates, which is a concrete number we can use to measure how fast our AI is actually learning.

Jane: It’s powerful because it moves beyond just finding *a* solution; it guarantees convergence to the *unique* stationary Markov perfect equilibrium under those specific conditions.

Lu: And they’ve also pushed the boundaries by extending it to state-dependent action spaces, which is much more realistic for systems with changing constraints.

Meng: That would be a big win for us if we could apply that to our current models where the constraints on what an agent can do change based on the situation unfolding.

Tom: The whole point is that this decentralized method lets agents learn policies from private bandit feedback, which is a huge step toward building more scalable and distributed AI systems.

Jane: So we’ve seen how this setup works, how it converges under specific mathematical conditions, and what it means for real-world AI deployment in complex interactions.

Lalam: I think this paper lays a very clear path for anyone looking to build distributed agents that can learn their roles effectively within a larger system.

Tom: We’ve covered the mechanics of how they estimate gradients and the convergence guarantees, but I'm curious what the next big challenge is here.

Jane: What do you think? Where does this leave us in terms of future research for this kind of decentralized learning?

Lu: I think focusing on those adaptive learning rates, which we touched on earlier, is where the next interesting direction lies. Moving from these theoretical guarantees to practical deployment under more volatile conditions is the next hurdle.

Meng: If we can make those step sizes truly agent-dependent and responsive to real-time environment feedback, that would be key for production systems.

Tom: It’s going to be a lot of work, but if we can nail that adaptation mechanism, it could really unlock how robust these AI agents are in the field.

Jane: Alright then, that’s our take on "Decentralized Bandit Learning of Markov Perfect Equilibria." Thanks for tuning in. Next up, we’ll be looking at how alignment training suppresses cultural knowledge in large language models.

Felix Höfer, –H. Mete Soner

University of Chicago · Princeton University

cs.LG, math.OC

Submitted: 2026-10-09

Updated: 2026-10-09

Comments: 23 pages, 1 figure

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 91/100

The gist: The gist: The fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium under strong monotonicity and sufficiently small time steps.

Key concepts

Decentralized Learning Setup: Agents learn independently by only observing their own state, action, and reward. They construct strategies based only on this local information. The learning happens along a single uninterrupted trajectory where agents update their beliefs simultaneously.
Stochastic Gradient Ascent with PSA: The algorithm updates agent strategies using stochastic gradient ascent. The required gradient is estimated using simultaneous perturbation stochastic approximation (PSA). This allows agents to refine their strategies by estimating the direction of improvement based on noisy, sampled data from the game.
Markov Perfect Equilibrium (MPE): In this context, an MPE is a stable set of strategies where no single agent can improve its outcome by unilaterally changing its strategy. The algorithm converges to this unique equilibrium pair $(\alpha^*, V^*)$, representing the optimal long-term behavior for all agents.
Episodic Learning: This extension applies the learning procedure to finite-horizon games. Instead of finding a static equilibrium, it seeks a Markov Perfect Equilibrium (MPE) that depends on time steps within an episode. The algorithm updates entries visited during the episode to find this time-dependent MPE.

Summary

The gist: The fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium under strong monotonicity and sufficiently small time steps.

Decentralized Learning Setup

The study focuses on decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents construct strategies based only on observations of the current state, their own realized action, and their own realized reward. The learning procedure operates along one uninterrupted trajectory.

Algorithm Mechanics

The algorithm updates agent strategies by stochastic gradient ascent with the required gradient estimated by simultaneous perturbation stochastic approximation. A perturbed action, the realized reward, and an estimate of the discounted continuation value yield a one-point estimate of each agent’s pseudo-gradient. The updates are synchronized across agents.

Convergence Guarantees

Under the regularity, strong-monotonicity, and small-time-step assumptions stated below, there exists a unique Markov perfect equilibrium pair (α⋆, V⋆). The algorithm satisfies αb n - α⋆∞ squared + Vb n - V⋆∞ → 0 almost surely. The convergence rate is established as A n + V n ≤ K√n.

Finite-Horizon Extension

The procedure can be extended to episodic finite-horizon learning where the target is an MPE rather than a Nash equilibrium of a static game. In this setting, the algorithm updates entries visited in that episode by αb i,n+1(Xn) = ProjUiαb i,n(Xn) + ηnDbi,n+1. The episodic algorithm converges almost surely to the unique finite-horizon MPE.

Key Assumptions

The analysis relies on several technical assumptions, including Assumption 2.1 (Rewards), which requires that for every i ∈ [N] and x ∈ X, the map a 7→ r i(x, a) is continuously differentiable. Assumption 2.3 (Time Step) requires that the time step h > 0 is sufficiently small so that µh > 0, κh 0, κh. Assumption 2.5 (Observations and numerical sequences) specifies conditions on the perturbations and learning rates such as δn → 0, λn → 0 0, 0. Assumption 2.6 (Exploration) requires that there is ζ > 0 such that P(y x, a) ≥ ζ, x, y ∈ X, a ∈ U 0 such that P(y x, a) ≥ ζ>.

Application Example

An illustrative example involves a discounted dynamic service game inspired by the strategic queueing model of Zhong, Gopalakrishnan, and Ward. The net payment is defined as r i(x, a) = p i a i - cE(a i) squared. The learning algorithm is applied to the centered actions u i:= a i - αc ∈ Ui:= [-ϱ, ϱ] when i ∈ S.

Complexity Analysis

The complexity analysis shows that for every x ∈ X, E[sn(Xn)] ≥ ζ squared E[Sn] − Kn-3p/4. This establishes the claim (2.14).

Episodic Learning Summary

For episodic learning, the algorithm updates tables with superscript n + 1 during the episode. The theorem states that there is a unique finite-horizon MPE (α⋆, V⋆). Its values satisfy V i,⋆ t(x) ≤ Cg + (T - t)hCr. The episodic algorithm converges almost surely: max t<T αb n t - α⋆ t∞ squared + max t≤T Vb n t - V⋆ t∞ → 0 <ref:2610.143332,The episodic algorithm converges almost surely: max t<T αb n t - α⋆ t∞ squared + max t≤T Vb n t - V⋆ t∞ → 0>.

Improvements for AI systems

Improved convergence guarantee for decentralized learning: The fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium under strong monotonicity of the negative running-reward gradients and sufficiently small time steps. This allows AI systems to learn optimal policies in complex, multi-agent environments without needing explicit knowledge of other agents' objectives.
Adaptive learning rates for continuous action spaces: The algorithm utilizes simultaneous perturbation stochastic approximation to update their actions, which is extended by allowing agent-dependent clocks and step sizes (motivated by prior work), enabling faster adaptation in dynamic settings where agents might operate on different timescales.
Efficient policy gradient estimation: Agents estimate the required pseudo-gradient using a one-point estimate derived from A perturbed action, the realized reward, and an estimate of the discounted continuation value yield a one-point estimate of each agent’s pseudo-gradient, effectively handling unknown continuation values as a vanishing stochastic-approximation bias.
Performance in episodic environments: The system can learn optimal policies for finite-horizon tasks by utilizing an episodic algorithm where tables are held fixed during an episode, allowing for the learning of time-dependent Markov perfect equilibria characterized by the updated Bellman operator (2.16).
Quantitative error bounds: The system can achieve a O(n − 1/2) convergence rate, meaning that the error in policy and value estimates converges to zero at a rate proportional to the square root of time, providing a predictable performance metric for learning progress.

Abstract

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an O(n-1/2) convergence rate and present a natural extension to episodic finite-horizon learning.