An Online Multiobjective Policy Gradient for Long-run Average-reward Markov Decision Process
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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]. 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).Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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]. Proposition 4. Algorithm 1 ensures convergence of the longrun average reward vector to the Target set T
Sketch of proof. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. Another important research direction is
to study sample efficiency of the algorithm presented in this
paper. Another important research direction is
to study sample efficiency of the algorithm presented in this
paper. As it stands now, the guarantees hold asymptotically. Another important research direction is
to study sample efficiency of the algorithm presented in this
paper. As it stands now, the guarantees hold asymptotically.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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 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¯(π)/∂ θ. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 • ⟨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. 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 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. 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
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. 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
′
)
. (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]. 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). 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). 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]. 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]. 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¯(π)
∂ θ . • Π denotes the projection of point a on set B i. ΠB(a) =
argminb∈B ∥a−b∥. • Π denotes the projection of point a on set B i. ΠB(a) =
argminb∈B ∥a−b∥. Π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∥
. 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
. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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 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. (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 paper says it
Where the paper says it
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 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 λ. 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
),λη ⟩. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. • ⟨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. • 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. • r represents a vector reward and r represents a scalar
reward. • π without superscript represents the joint policy i. • Π denotes the projection of point a on set B i. ΠB(a) =
argminb∈B ∥a−b∥.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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 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 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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]
.Where the paper says it
Where the paper says it
Where the paper says it
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 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
. 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.Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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 facingany u2 in U2.
-
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.
-
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. -
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
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Symbolic Control for Stochastic Systems via Finite Parity Games
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction