An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process

summary

The gist

An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process proposes a reinforcement learning framework for multi-objective decision-making where the agent seeks to…

In short

This work proposes an online reinforcement learning method to solve multi-objective decision-making problems where agents must optimize a vector of rewards instead of a single value. It uses a two-loop structure: an inner loop applies policy gradient updates, and an outer loop adaptively adjusts the reward vector's scalarization. This ensures the long-run average reward vector converges asymptotically to a predefined target set, even against adversarial actions.

Key concepts

Long-run Average Reward Vector ($ar{r}_t$)
This is the time-averaged sequence of rewards collected by an agent over a long period. Instead of looking at one reward per step, this vector summarizes the performance across all objectives simultaneously. The goal of the learning process is to make this vector settle near a desired target set.
Blackwell's Approachability Theorem
This theorem provides the theoretical guarantee that allows an agent to reach a specific target set of reward vectors. It states that if a policy can satisfy certain conditions related to its expected performance versus the target, it is guaranteed to approach that set over time, regardless of what an opponent does.
Adaptive Scalarization Vector ($oldsymbol{ heta}$)
This vector acts as a weighting mechanism that translates the multi-objective reward vector into a single scalar signal for the policy gradient updates. The outer loop of the algorithm iteratively updates this vector based on how close the current average reward is to the target set, guiding the agent toward it.
Recurrence Times ($ au_n$)
These are specific time intervals used in the algorithm to trigger policy updates for the outer loop. By waiting for a state to be revisited, the system ensures that parameter updates occur at meaningful points in time, which is crucial for enforcing convergence conditions related to ergodicity.

Terminology used across episodes

This episode discusses

The paper

An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process · Read on arXiv

Aalborg University

We propose a policy gradient algorithm for multiobjective decision-making on continuous state spaces, in which the long-run average of a reward vector must be steered into a target set despite an adversarial disturbance, by scalarizing the reward along the direction prescribed by Blackwell's Approachability Theorem instead of tuning weights by trial and error. Existing approachability-based learning is confined to countable state spaces, because the scalarization is updated at the visits to a recurrent state, which on a continuous state space has probability zero. We update it instead at the returns to a set after a minimum number of steps, show that a geometric drift condition, uniform over the policy class, controls the cycle lengths while the policy is being learned, and replace the parallel learners of the existing algorithm by a single two-timescale actor-critic. We show that the distance to the target set is asymptotically bounded by the per-cycle remainder from Blackwell's condition, and decompose this remainder into the errors of the actor, the policy class, the direction tracking and the return set. We illustrate the algorithm on a heating, ventilation, and humidity control problem with adversarial weather and occupancy.

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process".

Dev: Here's the gist of the paper. An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process proposes a reinforcement learning framework for multi-objective decision-making where the agent seeks to optimize a vector of rewards rather than a single scalar value.

Rosa: The objective is to ensure that the time-averaged reward vector converges asymptotically to a predefined target set.

Dev: Problem Formulation and Context The paper investigates how to handle inherently multiobjective sequential decision-making problems where controllers must optimize several often conflicting criteria simultaneously.

Rosa: Traditional RL frameworks typically assume a scalar reward signal, which fails to capture the complexity of environments requiring trade-offs between objectives.

Title and authors: Rosa: So we're looking at this paper today, "An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process," by Misra, Bujorianu, and Wisniewski. The title itself tells you a lot about what they're trying to do: they are using reinforcement learning to handle multi-objective decision making where the goal isn't just getting one good reward number, but steering the entire long-run average reward vector toward a specific target set.

Dev: Yeah, and it’s interesting because traditional reinforcement learning is usually built around optimizing a single scalar reward. This paper tackles that directly by proposing a framework where the agent tries to optimize this whole vector of rewards instead of just one number. It's about finding trade-offs between different objectives simultaneously, which is what we see in many complex real-world systems.

Taro: I wonder if this works well when the environment starts acting weird or adversarial, since that’s usually where standard RL breaks down. They introduce this dynamic scalarization mechanism guided by Blackwell’s Approachability Theorem to make sure the agent converges to that target set even when Player two is trying to mess with things <ref:2511.13034#pg1,dynamic scalarization mechanism guided by Blackwell’s Approachability Theorem>.

Rosa: Exactly. The paper suggests that instead of running a bunch of different reinforcement learning algorithms in parallel, which is computationally messy, you can use a single policy gradient scheme and adapt the scalarization vector online. That sounds much more practical for real-time control loops where you don't want to run multiple complex models simultaneously.

Dev: That’s the core idea, right? They exploit ergodicity to define these finite recurrence times, which lets them update that scalarization vector after every visit to a state. It ties the learning process directly into the convergence proof, which is pretty neat for showing stability under those long-run averages.

The paper's summary: Rosa: So what they actually do in this paper is propose this two-loop structure. You have an inner loop that uses a policy gradient method to estimate the error based on a scalarized reward, and then an outer loop that adaptively updates the scalarization vector. This outer loop is what steers the process toward the predefined target set T.

Dev: It sounds like they are essentially using Blackwell’s Approachability Theorem as their main guide. This theorem gives them a necessary and sufficient condition for how to choose a control policy so it can approach that target set even when facing any adversarial disturbance from Player two <ref:2511.13034#pg1>. They show how this leads to the scalar reward being defined as the inner product of the vector of rewards and this adaptive scalarization vector lambda.

Taro: I’m thinking about that adversarial part. If Player two is actively trying to keep us away from our target set, how does this single policy gradient scheme handle that pressure during those inner loop iterations <ref:2511.13034#pg1>? Does it just get stuck chasing the wrong direction?

Rosa: The paper addresses that by ensuring the inner loop enforces Blackwell’s condition at each step between visits to a recurrent state. This means every time the agent gets back to a familiar place, it has to check if its current policy is making progress toward the target set defined by lambda, which is calculated based on where the long-run average reward vector currently sits.

Dev: And that’s where they invoke Kac’s Theorem, which guarantees that these recurrence times converge to a finite number. That convergence of those recurrence times is what ultimately ensures the long-run average reward vector converges to the target set T via Proposition four of this work <ref:2511.13034#pg1>. It makes the asymptotic convergence solid.

The paper's improvements: Rosa: The main improvements they highlight are pretty significant when you compare this to prior work, especially something called thirteen <ref:2511.13034#pg1>. Previously, running J different reinforcement learning algorithms in parallel was shown to guarantee approachability if J is sufficiently large, but that’s just computationally impractical.

Dev: So their first big improvement is showing that you can achieve approachability using just a single policy gradient scheme instead of needing J different ones. That cuts down the complexity of the training setup dramatically, which is huge for practical applications.

Taro: And they also extend this method to systems with continuous state space by using function approximation. That means we’re not stuck on discrete states anymore; we can map those continuous states to feature vectors and let the policy use an inner product as its score, which opens up much more modeling possibilities.

Rosa: Right, so it’s about making it scalable for modern systems that have continuous inputs. They show they can take a two-player zero-sum Markov Game and turn it into a single agent Markov decision process by scalarizing the reward in this way, which is a neat trick for simplifying the learning structure.

Dev: And they also quantify the differential return G t, which is defined as how much the players' decisions at time t improve over the long-run average return r bar(pi), which then feeds into their value function and TD error calculations. This metric gives them a concrete way to measure progress toward that improvement, instead of just looking at the raw reward vector.

Conclusion: Rosa: So wrapping up, this paper on "An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process" shows us how to use an adaptive scalarization mechanism to steer the long-run average reward vector toward a target set T. It’s robust because they enforce Blackwell’s condition between visits to recurrent states, and they handle continuous state spaces with function approximation.

Dev: The implication is that we can build more robust controllers for complex systems where multiple objectives conflict, as long as the underlying Markov chain is ergodic. They prove that the long-run average reward vector converges to T, which means the agent eventually settles into a behavior that meets those multi-objective goals asymptotically.

Taro: From my side, I'm just thinking about how this applies when Player two isn't just playing randomly, but is actively trying to keep us away from T <ref:2511.13034#pg1>. Since the approachability theorem requires this condition to hold against any adversarial disturbance, it suggests that if a policy exists, we can find one that stays close to T despite their best efforts.

Rosa: Right. So in short, they’ve managed to use one policy gradient scheme instead of many, and they’ve made it work for continuous states under uncertainty. This paper gives us a solid theoretical foundation for designing RL systems that care about vectors of rewards rather than just single outcomes. That's what we have today with this work on "An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process."

More episodes

← Home