Optimal strategies in Markov decision processes with finitely additive evaluations

This paper demonstrates that while pure optimal strategies exist in infinite-horizon Markov decision processes with finite state and action spaces under diffuse charges satisfying the time value of money principle, optimal strategies (neither pure nor randomized) may fail to exist entirely if the aggregation charge is constructed without such assumptions.

The Gist

Here is an explanation of the paper using simple language, analogies, and metaphors.

The Big Picture: A Game with a Tricky Scorekeeper

Imagine you are playing a video game that never ends. Every turn, you make a move, get some points, and the game moves to the next level. Your goal is to get the highest score possible.

In most video games, the score is calculated in a simple way:

1. Discounted Sum: You care more about points you get now than points you get 100 years from now.
2. Long-Term Average: You just want to know your average points per turn over a very long time.

In both of these standard cases, there is a "Golden Rule" (a perfect strategy) that you can follow to win. You just need to figure out the right move for each situation, and you are set.

This paper is about a game with a very weird, tricky scorekeeper.

Instead of counting points normally, this scorekeeper uses a "Diffuse Charge." Think of this as a magical, invisible ruler that measures your performance.

• It doesn't care about when you get points (it treats time 1 and time 1,000,000 equally).
• It doesn't care about specific moments; it only cares about the "big picture" patterns.
• It's like a judge who ignores the first 99% of the game and only looks at the "spirit" of the whole performance, but in a way that is mathematically impossible to pin down.

The Main Discovery: The "Perfect" Strategy Doesn't Exist

The authors asked a simple question: "If we use this weird scorekeeper, is there still a perfect strategy to win?"

A previous researcher (Neyman) had shown that if the scorekeeper follows a specific "fairness rule" (called the Time Value of Money principle), then yes, there is a perfect strategy.

But this paper says: "No. If the scorekeeper is truly weird, there is NO perfect strategy."

Not a pure strategy (always doing the same thing), and not even a randomized strategy (flipping a coin to decide). No matter what you do, you can always be beaten by a slightly different move.

The Analogy: The "Even or Odd" Trap

To prove this, the authors built a specific trap called the "Even-or-Odd MDP."

Imagine a hallway with three rooms: Room 1, Room 2, and Room 3.

• Room 1: You have to choose between Door A (Top) and Door B (Bottom).
  • Door A: You get 1 point right now, but the next room gives you 0.
  • Door B: You get 0 right now, but the next room gives you 1.
• Room 2 & 3: You just walk through automatically and end up back in Room 1.

So, every two steps, you get exactly 1 point total.

• If you pick A, you get 1 then 0.
• If you pick B, you get 0 then 1.

The Catch: The scorekeeper (the Diffuse Charge) is split into two personalities:

1. Personality 1 (The Odd-Lover): Only cares about the points you get on Odd turns (1, 3, 5...).
2. Personality 2 (The Even-Lover): Only cares about the points you get on Even turns (2, 4, 6...).

The final score is the average of these two personalities.

The Dilemma

• To please Personality 1, you should always pick Door A (get 1 on odd turns).
• To please Personality 2, you should pick Door B often enough to get 1 on even turns.

Here is the impossible math:

• If you always pick Door A, you get a perfect score for Personality 1, but a terrible score for Personality 2. The average is low.
• If you always pick Door B, you get a perfect score for Personality 2, but a terrible score for Personality 1. The average is low.
• If you try to mix them (flip a coin), you get a "good" score for both, but never the maximum possible score.

The authors constructed a specific "magic ruler" (the charge) where the gap between "good" and "perfect" is a tiny, unbridgeable chasm. You can get closer to the perfect score by changing your strategy, but you can never actually reach it. It's like trying to touch the horizon; you can walk toward it forever, but you never arrive.

Why This Matters

1. The Limits of Planning: In the real world, we often assume that if we plan long enough, we can find the "best" way to do things. This paper shows that in complex, infinite systems with certain types of uncertainty, a "best" way might simply not exist.
2. The Danger of "Fairness": The paper highlights that if you try to be perfectly fair to every moment in time (ignoring the fact that time passes), you might create a situation where no one can ever win.
3. Mathematical Curiosity: It proves that even in a simple game with only 3 rooms and 2 doors, the math can get so twisted that the concept of a "winner" breaks down.

Summary in One Sentence

The paper proves that if you judge a player's performance using a very strange, time-blind scoring system, you can create a game where the player can get almost perfect, but mathematically cannot get a perfect score, no matter how hard they try.

Technical Summary

Here is a detailed technical summary of the paper "Optimal strategies in Markov decision processes with finitely additive evaluations."

1. Problem Statement

The paper investigates Infinite-Horizon Markov Decision Processes (MDPs) with finite state and action spaces. The core novelty lies in the evaluation criterion used by the decision maker. Unlike standard MDPs that use discounted sums or long-term average rewards, this paper considers an aggregation of the infinite stream of expected stage rewards using a diffuse charge (a finitely additive probability measure on the set of natural numbers $\mathbb{N}$ where every singleton has measure zero).

The central research question is: Does an optimal strategy always exist in such MDPs?

• Previous work by Neyman (2023) established that if the aggregation charge satisfies the "time value of money principle" (a specific condition related to patient valuations), a pure stationary optimal strategy exists.
• The authors ask whether this existence result holds for arbitrary diffuse charges, without the time value of money constraint.

2. Methodology and Framework

2.1 Mathematical Preliminaries

• Charges: The authors utilize the theory of finitely additive measures (charges) on $\mathbb{N}$. A charge $\mu$ is a mapping $\mu: 2^\mathbb{N} \to [0,1]$ that is finitely additive.
• Diffuse Charges: A charge is "diffuse" if $\mu(\{n\}) = 0$ for all $n \in \mathbb{N}$.
• Integration: The payoff is defined as the integral of the expected rewards with respect to the charge $\mu$:
  $$u_\mu(\sigma) = \int_{t \in \mathbb{N}} \mathbb{E}_\sigma[r_t] \, \mu(dt)$$
• Topology: The set of charges $\Delta_f$ is endowed with the topology of pointwise convergence. This space is compact and Hausdorff but not metrizable. This topological property is crucial for constructing the counterexample via accumulation points of sequences of charges.

2.2 The Model

• MDP Structure: Finite state space $S$, finite action spaces $A(s)$, bounded rewards $r(s,a)$, and transition probabilities $p(s'|s,a)$.
• Strategies: The authors consider both pure strategies (deterministic choices) and randomized (behavioral) strategies.
• Payoff: The value of the MDP is $v_\mu = \sup_{\sigma} u_\mu(\sigma)$. A strategy is optimal if it achieves this supremum.

3. Key Contributions and Results

3.1 Review of Existing Literature (Neyman, 2023)

The paper first recalls Neyman's result: If the aggregation charge $\mu$ satisfies the time value of money principle (equivalent to being a "patient valuation"), then there exists a pure stationary strategy that is optimal for all such charges simultaneously. This implies robustness in that specific subclass of charges.

3.2 Main Result: Non-Existence of Optimal Strategies (Theorem 3)

The primary contribution is a negative answer to the existence question for general diffuse charges. The authors construct a specific counterexample, the "Even-or-Odd MDP," combined with a "delicately constructed" aggregation charge $\mu$, such that no optimal strategy exists, neither pure nor randomized.

The Counterexample Construction:

1. The MDP:

   • States: $\{1, 2, 3\}$. Initial state: 1.
   • Actions in state 1: $T$ (Top) and $B$ (Bottom). States 2 and 3 have only one action.
   • Transitions: $T$ leads to state 2; $B$ leads to state 3. Both 2 and 3 transition deterministically back to 1.
   • Rewards:
     • State 1, Action $T$: Reward 1.
     • State 1, Action $B$: Reward 0.
     • State 2: Reward 0.
     • State 3: Reward 1.
   • Dynamics: The process cycles between state 1 and either 2 or 3. The decision maker effectively chooses at every odd stage (state 1) whether to get a reward of 1 now and 0 next, or 0 now and 1 next.

2. The Aggregation Charge ($\mu$):

   • The charge is constructed as a convex combination: $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$.
   • $\mu_0$: Concentrated on the set of odd numbers ($E_0$). It favors choosing action $T$ frequently.
   • $\mu^*$: Constructed as an accumulation point of a sequence of charges $\mu_n$. Each $\mu_n$ is concentrated on the set $E_n = \{k \cdot 2^n : k \in \mathbb{N}\}$.
   • The Conflict:
     • To maximize payoff under $\mu_0$, the agent must choose $T$ with frequency 1.
     • To maximize payoff under $\mu^*$, the agent must choose $B$ with a positive frequency (specifically, avoiding $T$ on the sets $E_n$).
     • The charge $\mu^*$ assigns measure 1 to every set $E_n$, yet the intersection of all $E_n$ is empty. This creates a situation where the agent cannot simultaneously satisfy the requirements of $\mu_0$ and $\mu^*$ to achieve the theoretical maximum.

3. The Proof of Non-Existence:

   • Claim 1: The value of the MDP is $v_\mu = 1$. The authors show that for any $\epsilon > 0$, there exists a strategy $\sigma_n$ that achieves a payoff of $1 - \epsilon$.
   • Claim 2: No strategy achieves exactly 1.
     • If a strategy yields payoff 1, the set of stages with expected reward $> 0.5$ must have $\mu$-measure 1.
     • This implies the set must have measure 1 under both $\mu_0$ and $\mu^*$.
     • However, the structural properties of the charge $\mu^*$ (derived from the sequence $E_n$) and the deterministic nature of the MDP (where $r_t + r_{t+1} = 1$) create a logical contradiction. A set cannot simultaneously have measure 1 under $\mu_0$ (requiring high frequency of $T$) and $\mu^*$ (requiring specific avoidance patterns) without violating the constraints of the MDP dynamics.
   • Conclusion: Since the supremum is 1 but is never attained, no optimal strategy exists.

3.3 Additional Findings

• Stationary vs. Pure Strategies: The paper provides an example (Example 4) showing that even if an optimal pure strategy exists for a specific charge, it may not be stationary.
• Non-Diffuse Charges: The authors briefly discuss charges that are not purely diffuse (i.e., have an atom). They show that if the charge has a countably additive component with positive weight, an optimal strategy may still fail to exist (Example 5), particularly when mixing discounted and average rewards.

4. Significance and Implications

1. Fundamental Limitation of Finitely Additive Measures: The paper demonstrates that the existence of optimal strategies in MDPs is not guaranteed when the evaluation criterion relies on general finitely additive measures. This contrasts sharply with standard MDP theory (discounted or countably additive average) where optimal strategies (often stationary) are guaranteed to exist.
2. Robustness of Neyman's Result: It clarifies the boundary of Neyman's (2023) theorem. The "time value of money principle" is not just a technical convenience; it is a necessary condition for the guarantee of optimal strategies in this general setting.
3. Topological Nuances: The construction relies heavily on the non-metrizable topology of the space of charges. It highlights how the compactness of the space of charges allows for the existence of "limit" charges that behave paradoxically compared to standard measures, leading to the non-existence of optimal policies.
4. Theoretical Depth: The result serves as a cautionary tale for decision theory models that aggregate infinite horizons using non-standard measures, showing that "supremum" does not always imply "maximum" in dynamic programming contexts with finitely additive evaluations.

In summary, the paper resolves a significant open question in the theory of MDPs by proving that optimal strategies do not necessarily exist when the payoff is evaluated via an arbitrary diffuse finitely additive charge, providing a rigorous counterexample that bridges measure theory and dynamic optimization.