Source-linked AI summary
Target Discounted Sum Problem on Markov Chains with Applications to Markov Decision Processes
Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran, Sasha Rubin, Moshe Y. Vardi
TL;DR
The paper addresses the open target discounted-sum existence problem through its stochastic variant on Markov chains. It proves a suffix-sum structural property, uses it with safety automata, and obtains pseudo-polynomial results for Markov chains and finite-memory MDP strategies.
Problem
The target discounted-sum problem asks whether an infinite sequence over a finite alphabet has discounted sum equal to a given target, and remains open for arbitrary rational discount factors.
Method
The paper proves that target-sum paths with infinitely many distinct suffix sums have probability zero and recognizes the remaining language with a deterministic safety automaton.
Results
The target probability for finite Markov chains, the MDP infimum, and the finite-memory MDP supremum are computable in pseudo-polynomial time, with the latter two attained by deterministic finite-memory strategies.
Takeaways & Limitations
The results provide an effective stochastic solution to target discounted sums on finite Markov chains and establish finite-memory optimality for the stated MDP values.
Takeaways & Limitations
The unrestricted MDP supremum remains open, and some finite MDPs have sup-optimal strategies only with infinite memory.
Abstract
from arXiv · showhide
The discounted sum is a way to aggregate a sequence of weights from a finite alphabet $Σ$, i.e., for a discount factor $λ$, the discounted sum of a sequence $w_0 w_1 w_2 \cdots$ over $Σ$ is $\sum_{i \in \mathbb{N}} w_i λ^i$. The target discounted-sum problem, which is currently open, asks, given $λ,Σ$ and a target $t$, whether there exists an infinite sequence over $Σ$ whose discounted sum is equal to $t$. We study and solve a probabilistic variant of this problem, i.e., the target discounted-sum problem on Markov chains. To do this, we prove that the event consisting of paths whose discounted sum is equal to the target and has infinitely many distinct suffix sums has probability zero. This structural property allows us to solve the target discounted-sum problem on Markov chains using an automata-theoretic technique. We apply our technical results to Markov decision processes with target discounted-sum objectives: we show that the infimum value and the finite-memory supremum value are computable in pseudo-polynomial time and are attained by deterministic finite-memory strategies.
1 Introduction
The paper formulates a stochastic version of the open target discounted-sum problem and solves it for finite Markov chains. It then applies the resulting techniques to target objectives in Markov decision processes.
- 1 Introduction: The target discounted-sum problem asks whether an infinite sequence over a finite alphabet has discounted sum exactly equal to a given target.The discounted sum aggregates sequence weights using powers of a rational discount factor.
- 1 Introduction: The Markov-chain variant computes the probability that a random path’s label sequence has discounted sum equal to the target.The instance includes a finite alphabet, rational discount factor and target, and a finite Markov chain with rational transition probabilities.
- 1 Introduction: For arbitrary rational discount factors, the desired Markov-chain probability is rational and computable in time polynomial in the chain size and numerical parameter values.The relevant parameters include the maximum absolute alphabet value and the denominators of the discount factor and target.
- 1 Introduction: The key structural result assigns probability zero to target-sum paths with infinitely many distinct suffix sums, enabling a safety-automaton and product-construction solution.The finitely distinct-suffix-sum sublanguage is recognized by an effectively constructable deterministic safety automaton.
- Applications.: For MDPs, the infimum and finite-memory supremum values are computable in pseudo-polynomial time and attained by deterministic finite-memory strategies.The unrestricted supremum remains open, and optimal strategies exhibit a dichotomy between pseudo-polynomially bounded and infinite memory.
- 1 Introduction: The work extends stochastic discounted-sum analysis beyond independent-weight distributions and prior cases requiring 1/λ to be an integer.In Markov chains, state-dependent transitions can produce atoms, unlike the independent-weight setting discussed for Bernoulli convolutions.
2 Preliminaries
The preliminaries define words, deterministic safety automata, finite Markov chains, paths, traces, and their induced probability spaces. They also establish the notation used to interpret measurable languages as Markov-chain events.
- Words: A word is an infinite symbol sequence, while finite words, prefixes, suffixes, concatenation, and positions provide the paper’s sequence notation.Positions start at 0, and the same notation is used for state sequences.
- Automata: A deterministic safety automaton has finite states, a unique transition for each state-symbol pair, and accepts words whose runs remain in safe states forever.Its accepted language is ω-regular.
- Markov chains: A finite Markov chain consists of states, an initial state, rational transition probabilities summing to one, and transition labels from the alphabet.Paths follow positive-probability transitions, and their traces are the corresponding infinite label sequences.
- Markov chains: Finite paths induce cylinder probabilities through products of transition probabilities, yielding the Markov chain’s probability space over infinite paths.The event space is generated by cylinder sets.
- Markov chains: A measurable language induces a measurable Markov-chain event consisting of paths whose traces belong to that language.Every ω-regular language is measurable.
- Markov chains: A bottom strongly connected component is a maximal strongly connected state set with no positive-probability transition leaving it.The event EBSCC(C) contains paths that enter some bottom strongly connected component.
3 The Target Discounted-Sum Problem on Markov Chains
The paper solves the target discounted-sum probability problem on finite Markov chains by separating finite and infinite suffix-sum behavior. It proves the infinite case has probability zero and reduces the finite case to a polynomial-size safety automaton and standard product computation.
- 3 The Target Discounted-Sum Problem on Markov Chains: The Markov-chain probability is computable in time polynomial in |C| · |Σ| · bq^2µ using the automaton product construction.The product computes the safety probability after the zero-probability infinite-suffix case is removed.
- 3 The Target Discounted-Sum Problem on Markov Chains: The target language is partitioned by whether a word has finitely or infinitely many distinct suffix sums.The finite-suffix class contains target words with a finite set of suffix discounted sums; the other class contains those with an infinite set.
- 3 The Target Discounted-Sum Problem on Markov Chains: For every finite Markov chain, paths in the target language with infinitely many distinct suffix sums have probability zero.This structural result holds for real alphabets, discount factors, and targets.
- 3 The Target Discounted-Sum Problem on Markov Chains: The finite-suffix language is recognized by a deterministic safety automaton with O(bq^2µ) states, constructible in O(bq^2µ · |Σ|) time.Here λ = p/q and t = a/b are in lowest terms, and µ is the maximum absolute alphabet value.
- 3.1 Proof of Theorem 3: In strongly connected chains, the target probability is either zero or every infinite path has the target discounted sum.The proof uses attainment of a maximum target probability, propagation along finite paths, and a contradiction based on suffix sums.
- 3.2 Proof of Theorem 4: The automata construction formalizes finite required suffix sums into explicit finite states, extending the approach beyond inverse-integer discount factors.For arbitrary rational discount factors, required suffix sums may otherwise form an infinite set.
4 Applications
The paper applies its Markov-chain results to target discounted-sum objectives in Markov decision processes. It defines strategies and finite-memory implementations through the induced Markov chain.
- 4 Applications: The MDP application studies algorithmic questions for target discounted-sum objectives using the preceding Markov-chain and automata results.The objective is to generate a path whose weight sequence has discounted sum exactly t.
- 4 Applications: An MDP consists of finite states, actions, rational transitions, and labels from a finite alphabet, with enabled actions constrained by transition probabilities.Strategies resolve nondeterministic action choices based on histories.
- 4 Applications: A finite-memory strategy uses a memory-update function and an action-selection distribution over enabled actions.The memory size is the cardinality of the strategy's finite memory set.
- 4 Applications: Fixing a strategy induces a Markov chain over labels; finite-memory strategies induce finite Markov chains.This provides the connection through which Markov-chain probability results apply to MDP strategies.
Optimal values and strategies
The paper characterizes optimal target discounted-sum values in MDPs through a finite-suffix-sum safety objective, obtaining computable infimum and finite-memory supremum values. Deterministic finite-memory optimal strategies can be synthesized, while unrestricted supremum optimization remains open.
- For finite-memory strategies, the automata-based values coincide with the corresponding target discounted-sum values, enabling the infimum result and finite-memory supremum result.
- The construction relates the original objective to the language of target paths with finitely many suffix sums, which is recognized by a pseudo-polynomial-size deterministic safety automaton.
- Inf-optimal and finite-memory supremum values are computable in pseudo-polynomial time, with deterministic strategies using pseudo-polynomial memory synthesized in the same time bound.
- A finite MDP can have a sup-optimal strategy while every such strategy requires infinite memory.
5 Conclusion
The paper solves stochastic target discounted-sum problems on finite Markov chains and lifts the results to MDPs. It leaves stochastic-game extensions as a follow-up question under a finite-memory restriction on the maximizing player.
- For rational discount factors and targets, target discounted-sum probabilities in finite Markov chains are rational and computable in pseudo-polynomial time.
- In MDPs, infimum and finite-memory supremum values are computable in pseudo-polynomial time and attained by deterministic finite-memory strategies.
- Extending the approach to turn-based stochastic games is identified as a follow-up question, with the proposed correspondence requiring finite-memory maximizing strategies.
A Proofs
The proofs establish a finite-state safety-automaton representation for target discounted sums with finitely many suffix sums and bound its size pseudo-polynomially. Product constructions then yield the Markov-chain and MDP algorithmic results.
- The denominator argument proves that every suffix-sum denominator divides a fixed product, using a prime-exponent contradiction over two cases.
- The finite-state bound follows by showing that an assumed maximal prime exponent cannot occur, because either it increases at the next suffix or persists at the previous suffix.
- The proof shows that every accepted word has target discounted sum t and only finitely many distinct suffix sums, while every such word is accepted by the safety automaton.
- The automaton's state space is pseudo-polynomially bounded in the alphabet range and rational encodings of the discount factor and target.
- Taking products with the safety automaton and applying standard safety algorithms gives pseudo-polynomial computation and deterministic finite-memory strategy synthesis for MDP objectives.