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

arXiv:2511.13034 · eess.SY, cs.SY, math.OC, math.PR · Submitted 2025-11-17 · Read on arXiv

Listen

Radio episode about this paper

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."

Aalborg University

eess.SY, cs.SY, math.OC, math.PR

Submitted: 2025-11-17

Updated: 2026-11-14

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

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…

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

Summary

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. p. 0

Where the paper says it

An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process Rahul Misra∗ , Manuela L. Bujorianu, and Rafał Wisniewski Abstract— We propose a reinforcement learning (RL) framework for multi-objective decision-making, where the agent seeks to optimize a vector of rewards rather than a single scalar value.

The objective is to ensure that the time-averaged reward vector converges asymptotically to a predefined target set. p. 0
Where the paper says it

Bujorianu, and Rafał Wisniewski Abstract— We propose a reinforcement learning (RL) framework for multi-objective decision-making, where the agent seeks to optimize a vector of rewards rather than a single scalar value. The objective is to ensure that the time-averaged reward vector converges asymptotically to a predefined target set.

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. Traditional RL frameworks typically assume a scalar reward signal, which fails to capture the complexity of environments requiring trade-offs between objectives. p. 0

Where the paper says it

INTRODUCTION Many real-world sequential decision-making (or control) problems are inherently multiobjective, requiring controllers to optimize several, often conflicting, criteria simultaneously. Traditional Reinforcement learning (RL) frameworks typically assume a scalar reward signal, which simplifies the learning process but fails to capture the complexity of environments where trade-offs between objectives are essential.

The authors categorize existing approaches into designing a scalar reward function or treating additional objectives as constraints in Constrained Markov Decision Processes (CMDP). p. 0
Where the paper says it

This can be seen in the papers [2], [3] where the authors design a domain-specific reward function and then adjust the scalarizing weights based on the result of simulations. The second approach is to treat the additional objectives as constraints and learn the solution for the Constrained Markov Decision Process (CMDP) [4].

The proposed method steers the long-run time average of the reward vector to a predefined Target set, which can coincide with the Pareto optimal set. p. 0
Where the paper says it

In this paper, we investigate another approach for handling multiple objectives based on Blackwell’s Approachability Theorem [9]. The central idea is to steer the long-run time average of the reward vector to a predefined Target set (that can be defined such that it coincides with the Pareto optimal set).

Algorithm Structure and Control Loops

The proposed algorithm employs a two-loop structure where an outer loop adaptively scalarizes the reward vector, and an inner loop consists of a standard Reinforcement Learning algorithm acting on the scalarized reward. The inner loop applies a Policy Gradient method, or more precisely, an actor-critic algorithm, to estimate the Temporal Difference (TD) error. p. 2

Where the paper says it

The outer loop will adaptively scalarize the reward vector, while the inner loop will consist of a standard Reinforcement Learning algorithm acting on the scalarized reward. For the inner loop, we will apply a Policy Gradient algorithm, or more precisely, an actor-critic algorithm, since we will also be estimating the Temporal Difference (TD) error.

This inner loop runs between successive visits to a designated recurrent state to enforce Blackwell’s condition at each iteration. p. 0
Where the paper says it

Assuming ergodicity, the Markov chain induced by the learned policies admits a stationary distribution, ensuring all states recur with finite return times. Our algorithm exploits this property by defining an inner loop that applies a policy gradient method (with baseline) between successive visits to a designated recurrent state, enforcing Blackwell’s condition at each iteration.

The outer loop updates the scalarization vector after each recurrence, ensuring convergence toward the target set. p. 0
Where the paper says it

This theorem enables adaptive updates of the scalarization vector to guarantee convergence toward the target set. Assuming ergodicity, the Markov chain induced by the learned policies admits a stationary distribution, ensuring all states recur with finite return times.

Theoretical Guarantees and Convergence

The theoretical foundation relies on Blackwell’s Approachability Theorem to guarantee that the control policy must satisfy to Approach the Target Set despite any adversarial disturbance. The approach is related to concepts like regret minimization, calibration, online optimization, and correlated equilibrium. p. 0

Where the paper says it

Blackwell’s Approachability Theorem [9] provides the necessary and sufficient condition (in the case of convex sets) that the control policy must satisfy to Approach the Target Set despite any adversarial disturbance. This method is related to the concepts of regret minimization, calibration, online optimization, and correlated equilibrium [10], [11].

The algorithm ensures convergence of the longrun average reward vector to the Target set T via Proposition 4. p. 4
Where the paper says it

Proposition 4. Algorithm 1 ensures convergence of the longrun average reward vector to the Target set T Sketch of proof.

This is achieved because the sequence of recurrent times converges to a finite number due to Kac’s Theorem. p. 4
Where the paper says it

The Policy gradient update rule (12) updates policy parameter θ in the direction of maximizing the long run average reward ⟨r¯(π),λ⟩. The sequence of recurrent times τ1,··· , τn → τ = 1 d π (x˜) , as n → ∞, for the recurrent state ˜x due to Kac’s Theorem 2.

Numerical Validation and Results

The approach was simulated on a numerical toy example simulating temperature and relative humidity in a house. The simulation demonstrated that the long-run average reward vector approaches the interior of the Target set T despite the adversary choosing worst-case points for the policies. p. 5

Where the paper says it

From the figure 1, it can be seen that the long-run average reward vector Approaches the interior of the Target set T. The long run average reward vector (in pink color) Approaches the target set T despite the adversary choosing worst-case points for the policies (u 1 0 , u 1 1 , u 1 2 ) selected by Player 1.

This numerical example validates that a single Policy gradient scheme can achieve Approachability to a target set in continuous state spaces via function approximation. p. 1
Where the paper says it

In contrast, we show Approachability using a single Policy gradient scheme. Secondly, we extend the method of [13] to systems with continuous state space via function approximation.

Contributions and Future Work

The paper's key contributions include showing Approachability using a single Policy gradient scheme instead of running J different RL algorithms in parallel. They extend the method to systems with continuous state space via function approximation. p. 1

Where the paper says it

In contrast, we show Approachability using a single Policy gradient scheme. Secondly, we extend the method of [13] to systems with continuous state space via function approximation.

Future work will involve extending the proposed approach to a more general setting with many players and studying the sample efficiency of the algorithm presented in this paper. p. 5
Where the paper says it

Future work will involve extending the proposed approach to a more general setting with many players. Another important research direction is to study sample efficiency of the algorithm presented in this paper.

The guarantees hold asymptotically, meaning convergence is guaranteed over time. p. 5
Where the paper says it

Another important research direction is to study sample efficiency of the algorithm presented in this paper. As it stands now, the guarantees hold asymptotically.

p. 5
Where the paper says it

Another important research direction is to study sample efficiency of the algorithm presented in this paper. As it stands now, the guarantees hold asymptotically.

Algorithm Summary

Algorithm 1 summarizes the steps, where the outer loop runs at timescale n, and the inner loop runs on timescale t that resets after τn is reached. The update rule for the policy parameter θ is given by θt+1 = θt +α∂ r¯(π)/∂ θ. p. 3

Where the paper says it

A common example is the softmax policy: πθ (u | x) = exp(θ ⊤φ(x,u)) ∑u ′∈U exp(θ ⊤φ(x,u ′)), φ(x,u) ∈ R l ,θ ∈ R l . The parameter θ is updated using the following gradient ascent rule, θt+1 = θt +α ∂ r¯(π) ∂ θ .

This update rule is derived from the Policy gradient Theorem with compatible function approximation. p. 3
Where the paper says it

The parameter θ is updated using the following gradient ascent rule, θt+1 = θt +α ∂ r¯(π) ∂ θ . (12) We can now state the Policy gradient Theorem with compatible function approximation that will allow us to obtain the expression for ∂ r¯(π)/∂ θ.

The final step shows that condition (19) of the Approachability Theorem is satisfied by showing that the inner loop achieves at least the value of the scalarized game in direction ληn+1. p. 4
Where the paper says it

Thus, after the inner loop, the controller achieves at least the value of the scalarized game in direction ληn+1 : ⟨ηn+1,ληn+1 ⟩ ≥ sup π 1 inf π 2 ⟨η(π 1 ,π 2 ),λη ⟩. Step 4: Theorem 3 requires that for every η ∈/ T, there exists a policy π 1 such that for all adversary policies π 2 : ⟨η(π 1 ,π 2 ) − ΠT (η),λη ⟩ ≥ 0.

Notation and Definitions

The paper introduces notation such as ∆(A) denoting a simplex on the finite set A = a1,···,an. The distance between a point and a set is defined as D(a,T):= infb∈T∥a−b∥ where∥·∥ is the standard Euclidean norm. p. 1

Where the paper says it

• ⟨a,b⟩ denotes the standard inner product between the vectors a and b. • Distance between point and set is defined as D(a,T) := infb∈T ∥a−b∥, where ∥·∥ is the standard Euclidean norm.

The long-run average reward vector r¯t is defined as r¯t:= 1/t∑n=1R(xn,un) (1). p. 0
Where the paper says it

In this paper, we investigate another approach for handling multiple objectives based on Blackwell’s Approachability Theorem [9]. The central idea is to steer the long-run time average of the reward vector to a predefined Target set (that can be defined such that it coincides with the Pareto optimal set).

The goal of Player 1 is defined as lim t→∞D(r¯t,T) = 0 Pµπ a. p. 1
Where the paper says it

The functional form of transition dynamics P and the reward function R are unknown to both players; instead, the players observe the history h i t = x0,u i 0 ,x1,u i 1 ,··· ,xt , where i = {1,2} denotes the player. Thus, we have a Reinforcement learning problem as each player’s goal is to choose control actions that reinforce the desired outcome (defined in II.

s. for any u2 ∈ U2 (5). The state transition matrix Pπ between two states x and x′ is defined as Pπ(x,x′) = ∑u1∑u2π1(u1x)π2(u2x)P(x' x,u1,u2). The reward vector generated by following the joint policy π is defined as Rπ(x):= ∑u π(u x)R(x,u). p. 2
Where the paper says it

For a given joint policy π, we define a state transition matrix P π between two states x and x ′ as, P π (x,x ′ ) = ∑ u 1 ∑ u 2 π 1 (u 1 | x)π 2 (u 2 | x)P(x ′ | x,u 1 ,u 2 ). Similarly, we can define R π (x) := ∑u π(u | x)R(x,u) as the reward vector generated by following the joint policy π.

The differential return Gt quantifies the improvement over the long-run average return ¯r(π) due to players decisions at time t +1 being u 1t+1,u 2t+1 with state being xt+1. p. 3
Where the paper says it

The Differential return Gt quantifies the improvement over the long-run average return ¯r(π) due to players decisions at time t +1 being u 1 t+1 ,u 2 t+1 with state being xt+1, at time t +2 being u 1 t+2 ,u 2 t+2 with state being xt+2, and so on. Thus, it follows that if Gt ≈ 0, then no benefit or loss was gained compared to the long-run average reward.

The Differential Value function for the game is defined as Vπ (x):= Eπ [Gt xt = x] (9). p. 3
Where the paper says it

Thus, it follows that if Gt ≈ 0, then no benefit or loss was gained compared to the long-run average reward. Based on the definition of Gt , the Differential Value function for the game is defined as Vπ (x) := Eπ [Gt | xt = x] (9) The Differential value function satisfies a Bellman-like equation [18] (sometimes referred to as the discrete Poisson Equation [20]) or more precisely, Vπ (x) = Eπ r −r¯(π) +Vπ (x ′ ) (10) Generally, the term g := Eπ [r¯(π)] is added on both sides to obtain the Bellman-like equation, Vπ (x) +g = Eπ r +Vπ (x ′ ) .

The Qfunction (value function given ut = u) is defined as Qπ (x,u):= Eπ [Gt xt = x,ut = u]. p. 3
Where the paper says it

(11) Here, the term Vπ (x) quantifies the effect of starting at state x (or the bias to state x). Similarly, we can define the Qfunction (value function given ut = u) as follows, Qπ (x,u) := Eπ [Gt | xt = x,ut = u].

The policy gradient theorem provides the expression for ∂ r¯(π)/∂ θ which is given by ∑x dπ(x)∑u∂ logπθ (x,u)∂ θ δ(x,u). p. 3
Where the paper says it

Theorem 1 (Policy Gradient Theorem [19], [22]). The gradient of average reward is given by the following expression, ∂ r¯(π) ∂ θ = ∑x d π (x)∑u ∂ logπθ (x,u) ∂ θ δ(x,u), (13) where δ(x,u) is the TD error calculated at time t as follows, δ(xt ,ut) = r(xt ,ut)−gˆt−1 +Vˆ t−1(xt+1)−Vˆ t−1(xt).

The TD error δt is calculated as δ(xt,ut) = r(xt,ut)-gˆt-1 +Vˆt-1(xt+1)-Vˆt-1(xt). p. 3
Where the paper says it

Theorem 1 (Policy Gradient Theorem [19], [22]). The gradient of average reward is given by the following expression, ∂ r¯(π) ∂ θ = ∑x d π (x)∑u ∂ logπθ (x,u) ∂ θ δ(x,u), (13) where δ(x,u) is the TD error calculated at time t as follows, δ(xt ,ut) = r(xt ,ut)−gˆt−1 +Vˆ t−1(xt+1)−Vˆ t−1(xt).

The update rule for the value function is Vˆ(xt) = Vˆ(xt) +βδt. p. 3
Where the paper says it

Note that, Vˆ ≈ ⟨ρ,ψ(x,u)⟩, where ψ : X ×U → R l are the features of the value function and ρ ∈ R l are the corresponding parameters updated via gradient descent in the direction that minimizes the following least squares error, ρt+1 = ρt −β∇ρL (ρ), L (ρ) = 1 t t ∑ n=1 (Vˆ(xt)−Gt) 2 , (16) where Vˆ(xt) = ⟨ρt ,ψ(xt ,ut)⟩. Substituting (16) in (14) results in the following update rule, Vˆ(xt) = Vˆ(xt) +βδt , gˆt+1 = gˆt +βgδt , (17) where β and βg are step-sizes that satisfy the Robbins Monroe conditions [23].

The update rule for the average reward estimate is gˆt+1 = gˆt +βgδt. p. 3
Where the paper says it

Note that, Vˆ ≈ ⟨ρ,ψ(x,u)⟩, where ψ : X ×U → R l are the features of the value function and ρ ∈ R l are the corresponding parameters updated via gradient descent in the direction that minimizes the following least squares error, ρt+1 = ρt −β∇ρL (ρ), L (ρ) = 1 t t ∑ n=1 (Vˆ(xt)−Gt) 2 , (16) where Vˆ(xt) = ⟨ρt ,ψ(xt ,ut)⟩. Substituting (16) in (14) results in the following update rule, Vˆ(xt) = Vˆ(xt) +βδt , gˆt+1 = gˆt +βgδt , (17) where β and βg are step-sizes that satisfy the Robbins Monroe conditions [23].

The parameter θ is updated using the gradient ascent rule θt+1 = θt +α∂ r¯(π)/∂θ. p. 3
Where the paper says it

A common example is the softmax policy: πθ (u | x) = exp(θ ⊤φ(x,u)) ∑u ′∈U exp(θ ⊤φ(x,u ′)), φ(x,u) ∈ R l ,θ ∈ R l . The parameter θ is updated using the following gradient ascent rule, θt+1 = θt +α ∂ r¯(π) ∂ θ .

The projection of a point s on set B is defined as ΠB(a) = argminb∈B∥a−b∥. p. 1
Where the paper says it

• Π denotes the projection of point a on set B i. ΠB(a) = argminb∈B ∥a−b∥.

p. 1
Where the paper says it

• Π denotes the projection of point a on set B i. ΠB(a) = argminb∈B ∥a−b∥.

The unit vector λs pointing in the direction of the Target set T from s is λs = ΠT (s)−s∥ΠT (s)−s∥. p. 4
Where the paper says it

ΠT (s) be the projection of s on the Target set T. Then the unit vector λs pointing in the direction of the Target set T from s is λs = ΠT (s)−s ∥ΠT (s)−s∥ .

The Blackwell condition requires that for any point s ∈/ T, there exists a policy π 1 such that ⟨η(π 1,π 2)−ΠT (s),λs⟩ ≥ 0 for any u2 ∈ U2. p. 4
Where the paper says it

Player 1 can Approach the set T ⊂ R k as per definition II. 1 if the following condition holds: For any point s ∈/ T , there exists a policy π 1 s such that, ⟨η(π 1 s ,π 2 s )−ΠT (s),λs⟩ ≥ 0, for any u2 ∈ U 2 .

The Approaching policy is chosen as follows: If xt = x and the average reward vector upto time t, ˜ r¯t ∈/ T, play π 1r¯t until the next visit to state x; otherwise play arbitrarily ˜until the next return to state x. p. 4
Where the paper says it

1 if the following condition holds: For any point s ∈/ T , there exists a policy π 1 s such that, ⟨η(π 1 s ,π 2 s )−ΠT (s),λs⟩ ≥ 0, for any u2 ∈ U 2 . (19) Furthermore, the Approaching policy is chosen as follows: If xt = x and the average reward vector upto time t, ˜ r¯t ∈/ T , play π 1 r¯t until the next visit to state x; otherwise play arbitrarily ˜ until the next return to state x.

p. 4
Where the paper says it

1 if the following condition holds: For any point s ∈/ T , there exists a policy π 1 s such that, ⟨η(π 1 s ,π 2 s )−ΠT (s),λs⟩ ≥ 0, for any u2 ∈ U 2 . (19) Furthermore, the Approaching policy is chosen as follows: If xt = x and the average reward vector upto time t, ˜ r¯t ∈/ T , play π 1 r¯t until the next visit to state x; otherwise play arbitrarily ˜ until the next return to state x.

The Blackwell condition (19) is satisfied by showing that⟨ηn+1,ληn+1⟩ ≥ supπ 1infπ 2⟨η(π 1,π 2),lh⟩ ≥ ⟨ΠT (η),lh⟩. p. 4
Where the paper says it

Since λη is the unit normal from η to ΠT (η), this condition is equivalent to, ⟨ηn+1,ληn+1 ⟩ ≥ sup π 1 inf π 2 ⟨η(π 1 ,π 2 ),λη ⟩ ≥ ⟨ΠT (η),λη ⟩. Thus condition (19) is satisfied.

The final result is that the long-run average reward vector converges to the Target set T. p. 5
Where the paper says it

CONCLUSIONS We have developed an algorithm for multi-objective RL that is robust to adversarial disturbances, and we show that the policy gradient approach can be used for satisfying the Blackwell condition in Proposition 4. The proposed algorithm has been simulated on a numerical example which also demonstrates that the long-run average reward vector converges to the Target set.

p. 5
Where the paper says it

CONCLUSIONS We have developed an algorithm for multi-objective RL that is robust to adversarial disturbances, and we show that the policy gradient approach can be used for satisfying the Blackwell condition in Proposition 4. The proposed algorithm has been simulated on a numerical example which also demonstrates that the long-run average reward vector converges to the Target set.

Pruning redundant reasoning tokens

The paper's focus is on developing 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. This is important because traditional RL frameworks assume scalar rewards, which fails to capture environments where trade-offs between objectives are essential. p. 0

Where the paper says it

INTRODUCTION Many real-world sequential decision-making (or control) problems are inherently multiobjective, requiring controllers to optimize several, often conflicting, criteria simultaneously. Traditional Reinforcement learning (RL) frameworks typically assume a scalar reward signal, which simplifies the learning process but fails to capture the complexity of environments where trade-offs between objectives are essential.

The authors investigate an approach based on Blackwell’s Approachability Theorem to steer the long-run time average of the reward vector to a predefined Target set. p. 0
Where the paper says it

In this paper, we investigate another approach for handling multiple objectives based on Blackwell’s Approachability Theorem [9]. The central idea is to steer the long-run time average of the reward vector to a predefined Target set (that can be defined such that it coincides with the Pareto optimal set).

How the training signal is built

The training signal involves two main components: an inner loop applying a Policy Gradient algorithm for scalarized rewards and an outer loop that adaptively updates the scalarization vector. The inner loop uses recurrence times to artificially create time instances where parameters can be updated. p. 2

Where the paper says it

Instead, we need to artificially create time instances where we can update the desired parameters. This can be done using recurrence times that indicate when a predefined state ˜x has been observed in the trajectory.

The policy gradient update rule is derived from the Policy gradient Theorem with compatible function approximation, which allows sampling from on-policy visited states without knowledge of the stationary distribution. p. 3
Where the paper says it

(14) Here V and ˆ g is approximated via gradient descent with a ˆ compatible function approximation that minimizes error (see (16), (17)). This theorem will allow us to sample from the on-policy visited states without knowledge of the stationary distribution.

Where the gains come from

The gains stem from exploiting ergodicity to define finite-time recurrence times τn for a state ˜x. This allows the algorithm to update the scalarizing vector λ by calculating the projection of ¯r onto the target set T at each recurrence time. p. 4

Where the paper says it

At time τn, we update the scalarizing vector λ by calculating the projection of ¯r onto the target set T. This leads us to the inner loop, where Player 1 applies the Policy Gradient algorithm based on the equations (12)-(17) to find the Policy for the given direction λ.

The outer loop's gradient ascent on ¯r(π) increases ⟨η(π),λη(π)⟩, which is shown to be greater than or equal to the supremum over all policies. This ensures that the controller achieves at least the value of the scalarized game in direction ληn+1. p. 4
Where the paper says it

Then we can show that, ⟨ηn+1,ληn+1 ⟩ ≥ ⟨ηn,ληn ⟩. Thus, after the inner loop, the controller achieves at least the value of the scalarized game in direction ληn+1 : ⟨ηn+1,ληn+1 ⟩ ≥ sup π 1 inf π 2 ⟨η(π 1 ,π 2 ),λη ⟩.

The numerical results confirm that the long-run average reward vector approaches the interior of Target set T despite adversarial choices. p. 5
Where the paper says it

From the figure 1, it can be seen that the long-run average reward vector Approaches the interior of the Target set T. The long run average reward vector (in pink color) Approaches the target set T despite the adversary choosing worst-case points for the policies (u 1 0 , u 1 1 , u 1 2 ) selected by Player 1.

Conclusion and Future Directions

The paper successfully developed an algorithm for multi-objective RL that is robust to adversarial disturbances, demonstrating that the policy gradient approach can satisfy the Blackwell condition. Future work will focus on extending this approach to a more general setting with many players and studying sample efficiency of the algorithm presented in this paper. p. 5

Where the paper says it

Future work will involve extending the proposed approach to a more general setting with many players. Another important research direction is to study sample efficiency of the algorithm presented in this paper.

The guarantees hold asymptotically, meaning convergence is guaranteed over time. The simulation on a simple numerical toy example confirms that the long-run average reward vector converges to the Target set T. p. 5
Where the paper says it

CONCLUSIONS We have developed an algorithm for multi-objective RL that is robust to adversarial disturbances, and we show that the policy gradient approach can be used for satisfying the Blackwell condition in Proposition 4. The proposed algorithm has been simulated on a numerical example which also demonstrates that the long-run average reward vector converges to the Target set.

The notation ∆(A) denotes a simplex on the finite set A = a1,···,an i.e. for all ai ∈ A, ai ≥ 0, and ∑ n i=1 ai = 1. The notation P a b represents a probability measure induced by a,b and E a b is the corresponding expectation operator. p. 1

Where the paper says it

for all ai ∈ A, ai ≥ 0, and ∑ n i=1 ai = 1. • The notation P a b represents a probability measure induced by a,b and E a b is the corresponding expectation operator.

The distance between point and set is defined as D(a,T):= infb∈T∥a−b∥ where∥·∥ is the standard Euclidean norm. p. 1
Where the paper says it

• ⟨a,b⟩ denotes the standard inner product between the vectors a and b. • Distance between point and set is defined as D(a,T) := infb∈T ∥a−b∥, where ∥·∥ is the standard Euclidean norm.

The notation r represents a vector reward and r represents a scalar reward. p. 1
Where the paper says it

• Distance between point and set is defined as D(a,T) := infb∈T ∥a−b∥, where ∥·∥ is the standard Euclidean norm. • r represents a vector reward and r represents a scalar reward.

The notation π without superscript represents the joint policy i. p. 1
Where the paper says it

• r represents a vector reward and r represents a scalar reward. • π without superscript represents the joint policy i.

e. π = (π 1,π 2). The projection of point a on set B is defined as ΠB(a) = argminb∈B∥a−b∥ i. p. 1
Where the paper says it

• Π denotes the projection of point a on set B i. ΠB(a) = argminb∈B ∥a−b∥.

e. ΠB(a) = argminb∈B∥a−b∥.

We consider a Zero-Sum Markov Game from Player 1’s perspective (i.e. Player 2’s actions can be arbitrary) that is defined as M:= (X,U 1,U 2,P,R,T,µ). p. 1

Where the paper says it

PROBLEM FORMULATION We consider a Zero-Sum Markov Game from Player 1’s perspective (i. Player 2’s actions can be arbitrary) that is defined as M := (X,U 1 ,U 2 ,P,R,T,µ), where X is the state space, U 1 and U 2 are the control action spaces, P : X ×U 1 × U 2 → ∆(X) is the transition probability, R : X ×U 1 ×U 2 → R k is the reward vector consisting of k objectives, T ∈ R k is the predefined Target set for Player 1, and µ ∈ ∆(X) is the initial distribution of states.

The joint control action taken by the players at time t is denoted by ut:= (u 1t,u 2t). p. 1
Where the paper says it

At time t ∈ {0,1,2,··· }, each player observes the state xt ∈ X, picks a control actions u 1 t ∈ U 1 (or u 2 t ∈ U 2 ). The joint control action taken by the players at time t is denoted by ut := (u 1 t ,u 2 t ).

The players then observe a sample of the reward vector rt:= R(xt,u 1t,u 2t). p. 1
Where the paper says it

The joint control action taken by the players at time t is denoted by ut := (u 1 t ,u 2 t ). The players then observe a sample of the reward vector rt := R(xt ,u 1 t ,u 2 t ), and transition to the new state xt+1 ∈ X based on the transition dynamics P.

The time-averaged reward vector r¯t is defined as r¯t:= 1/t∑n=1R(xn,un) (1). p. 0
Where the paper says it

The central idea is to steer the long-run time average of the reward vector to a predefined Target set (that can be defined such that it coincides with the Pareto optimal set). The steering is done as follows: First, we calculate the projection of the time-averaged reward vector on the Target set.

Long-Run Average Reward Vector

For a given joint policy π, the long-run average reward vector is defined as r¯(π):= lim t→∞ 1/tEµπ"t∑n=0R(xn,un) = Edπ [R(x,u)] (4). The goal of Player 1 is defined as Definition II. p. 1

Where the paper says it

The functional form of transition dynamics P and the reward function R are unknown to both players; instead, the players observe the history h i t = x0,u i 0 ,x1,u i 1 ,··· ,xt , where i = {1,2} denotes the player. Thus, we have a Reinforcement learning problem as each player’s goal is to choose control actions that reinforce the desired outcome (defined in II.

1. Given the initial distribution µ, a policy π 1⋆ of Player 1 Approaches the target set T⊂ R k if lim t→∞D(r¯t,T) = 0 Pµπ a. p. 2
Where the paper says it

We can now define Player 1’s objective more precisely as, Definition II. Given the initial distribution µ, a policy π 1⋆ of Player 1 Approaches the target set T ⊂ R k if lim t→∞ D(r¯t ,T) = 0 P µ π a.

s. for any u2 ∈ U2 (5). The assumption of ergodicity ensures the existence of the stationary distribution dπ satisfying dπPπ = dπ. p. 3
Where the paper says it

Theorem 2 (Kac’s Theorem [20]). If the Markov chain induced by the joint policy π is ergodic and admits a state x˜ ∈ X with positive recurrent time τn, then if dπ is the stationary distribution for the induced Markov chain, then d π (x˜) = 1 Eπ [τn] .

The long-run average reward vector is defined as r¯(π):= lim t→∞ 1/tEµπ"t∑n=0R(xn,un) = Edπ [R(x,u)] (4).

Approachability Theorem Application

The Approachability Theorem for Markov Games states that Player 1 can Approach the set T⊂ R k as per definition II.1 if the following condition holds: For any point s ∈/ T, there exists a policy π 1s such that, ⟨η(π 1s,π2s)−ΠT (s),λs⟩ ≥ 0 for any u2 ∈ U2. p. 4

Where the paper says it

Player 1 can Approach the set T ⊂ R k as per definition II. 1 if the following condition holds: For any point s ∈/ T , there exists a policy π 1 s such that, ⟨η(π 1 s ,π 2 s )−ΠT (s),λs⟩ ≥ 0, for any u2 ∈ U 2 .

The Approaching policy is chosen as follows: If xt = x and the average reward vector upto time t, ˜ r¯t ∈/ T, play π 1r¯t until the next visit to state x; otherwise play arbitrarily ˜until the next return to state x. The Blackwell condition (19) is satisfied by showing that⟨ηn+1,ληn+l+1⟩ ≥ supπ 1infπ 2⟨η(π 1,π 2),lh⟩ ≥ ⟨ΠT (η),lh⟩. p. 4
Where the paper says it

Since λη is the unit normal from η to ΠT (η), this condition is equivalent to, ⟨ηn+1,ληn+1 ⟩ ≥ sup π 1 inf π 2 ⟨η(π 1 ,π 2 ),λη ⟩ ≥ ⟨ΠT (η),λη ⟩. Thus condition (19) is satisfied.

The final result is that the long-run average reward vector converges to the Target set T.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Adaptive scalarization for multi-objective reinforcement learning allows an agent to steer its long-run average reward vector to a predefined target set T, ensuring that the time-averaged reward vector converges asymptotically to a predefined target set.

  2. The system can handle complex, conflicting objectives by using Blackwell's Approachability Theorem, which provides a necessary and sufficient condition (in the case of convex sets) that the control policy must satisfy to Approach the Target Set despite any adversarial disturbance.

  3. The algorithm is robust to adversarial disturbances because it utilizes a two-loop structure where the outer loop adapts the scalarization vector and the inner loop applies a policy gradient method, guaranteeing Approachability to a target set even when facing any u2 in U2.

  4. The improved AI system can learn optimal control policies in continuous state spaces by employing function approximation, mapping state-action pairs to feature vectors such that the policy uses an inner product as its score.

  5. The system can perform robust control under uncertainty by calculating a differential return Gt that quantifies the improvement over the long-run average return r bar(pi) due to players decisions, enabling policy updates based on this metric.

  6. The agent can be trained on trajectories without terminating episodes, as it uses recurrence times that indicate when a predefined state x has been observed in the trajectory to create update instances for the outer loop of the algorithm.

Abstract

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.

Sources

Related papers