Source-linked AI summary
Mean-Variance Optimization in Markov Decision Processes
Shie Mannor, John Tsitsiklis
TL;DR
The paper studies how to optimize mean reward while accounting for the variance of cumulative reward in finite-horizon MDPs. The paper compares policy classes and uses multicriteria or constrained MDP methods to develop pseudopolynomial algorithms and prove hardness results. Mean-variance optimization is typically NP-hard, while some cases admit pseudopolynomial exact or approximation algorithms.
Problem
The paper studies how to optimize mean reward while accounting for the variance of cumulative reward in finite-horizon MDPs.
Source: §I · p. 1Method
The paper compares policy classes and uses multicriteria or constrained MDP methods to develop pseudopolynomial algorithms and prove hardness results.
Source: §I · p. 2, §VII · p. 20Results
Mean-variance optimization is typically NP-hard, while some cases admit pseudopolynomial exact or approximation algorithms.
Source: §VII · pp. 19–20Takeaways & Limitations
In some policy-class comparisons, one class can strictly exceed another in performance.
Source: §III · p. 5The reported scope is finite-horizon MDPs; concave-utility and risk-constrained cases are also flagged as approximation interests.
Source: §VII · pp. 19, 21
Abstract
from arXiv · showhide
We consider finite horizon Markov decision processes under performance measures that involve both the mean and the variance of the cumulative reward. We show that either randomized or history-based policies can improve performance. We prove that the complexity of computing a policy that maximizes the mean reward under a variance constraint is NP-hard for some cases, and strongly NP-hard for others. We finally offer pseudopolynomial exact and approximation algorithms.
I. INTRODUCTION
The paper studies finite-horizon MDPs where decisions balance expected cumulative reward against its variance, a criterion relevant to financial and engineering objectives. It examines policy performance and computational complexity, then develops pseudopolynomial algorithms alongside hardness results.
I. INTRODUCTION
- The authors contrast mean-variance optimization with coherent risk measures, which optimize worst-case performance over a family of probabilistic models.The introduction notes that mean-variance optimization lacks some desirable properties of coherent risk measures and can yield counterintuitive policies.Source: §I · pp. 1–2
- Mean-variance optimization lacks Bellman’s principle of optimality, and unexpectedly large early rewards can make a decision maker seek later losses to keep variance small.Variance is nonlinear in the process probability measure, although the first and second moments are linear.Source: §I · p. 2
- Mean-variance criteria arise in financial rebalancing and in engineering processes seeking both greater output and more consistent manufactured components.The introduction describes one-year fund returns and deposited material amounts as examples.Source: §I · p. 2
- The paper develops pseudopolynomial exact and approximation algorithms while establishing NP-hardness results for mean-variance optimization.The authors say these hardness results leave little hope for significant algorithmic improvement.Source: §I · p. 2
- Performance typically improves strictly when more general policy classes are allowed.The paper compares policy classes before establishing their computational complexity and developing algorithms.Source: §I · p. 3
II. THE MODEL
This section sets out the finite-horizon MDP setting and the policy classes used to study mean-variance objectives. Policies may condition on the current state, accumulated reward, history, or independent randomization.
A. Markov Decision Processes
- The model is finite-horizon, with finite state, action, and reward spaces and specified transition and immediate-reward distributions.The process begins at an initial state, and actions are chosen at each stage before rewards and the next state are realized.Source: §II · p. 3, A. Markov Decision Processes · pp. 3–4
B. Policies
- A deterministic policy is a stage-indexed mapping from the permitted information to an action; policies may use history or augmented state and reward information.The policy classes distinguish conditioning on the state, on (state, cumulative reward), and on additional randomization.Source: B. Policies · p. 4
- Randomized policies use independent uniform random variables in addition to process history when selecting actions.The paper defines these variables as independent of everything else and allows actions to depend on their sequence through the current stage.Source: B. Policies · p. 4
C. Performance Criteria
The paper evaluates finite-horizon policies by the mean and variance of cumulative reward, including mean–variance constrained objectives. It shows that randomization and access to reward history can improve performance, although some policy classes are equivalent.
C. Performance Criteria
- The criteria are the cumulative reward’s mean and variance, and the decision problem asks whether a policy can meet a lower mean bound and an upper variance bound.The paper also considers maximizing expected cumulative reward subject to a variance bound, or minimizing variance subject to a mean bound.Source: C. Performance Criteria · pp. 4–5
III. COMPARISON OF POLICY CLASSES
- The paper defines one policy class as inferior when another can match its yes-instances and strictly outperform it on at least one instance.Its comparisons find Πt,s inferior to Πt,s,w and Πt,s,u inferior to Πt,s,w,u; Πt,s,w is also inferior to Πh.Source: §III · p. 5, B. Information Improves Performance · p. 6
A. Randomization Improves Performance
- Randomization can strictly improve performance: when 0 < p ≤ 1/4, choosing action b with probability p is feasible and yields positive expected reward where the feasible deterministic policy yields zero.The example establishes that deterministic policies are inferior to randomized policies for the policy classes considered there.Source: A. Randomization Improves Performance · pp. 5–6
B. Information Improves Performance
- Access to cumulative reward history can improve performance over policies using only time and state, including when the variance constraint is zero.In the example, conditioning the next action on the previous reward gives total reward 1 with zero variance, whereas the compared time-and-state policies achieve expected reward zero.Source: B. Information Improves Performance · pp. 6–7
- The classes Πt,s,w,u and Πh,u are an exception to the general performance gains from greater information, because the paper shows them equivalent.The stated equivalence is referenced to Theorem 6.Source: B. Information Improves Performance · p. 6
IV. COMPLEXITY RESULTS
The paper establishes NP-hardness for several policy classes and strong NP-hardness for two more restricted classes. Its reductions use zero-variance instances, including a construction from 3SAT.
IV. COMPLEXITY RESULTS
- MV-MDP is NP-hard for Πt,s,w, Πt,s,w,u, Πh, and Πh,u.The proof targets the special case of deciding whether a policy can achieve zero reward variance.Source: §IV · p. 7
- MV-MDP is strongly NP-hard for Πt,s and Πt,s,u.The proof uses a reduction from 3SAT.Source: §IV · p. 8
- In the 3SAT construction, each clause state cj offers three actions selecting its clause’s literals, transitions to the associated yi state, and gives immediate reward 1 for an unnegated literal and −1 for a negated one.Source: §IV · p. 9
V. EXACT ALGORITHMS
The paper develops exact pseudopolynomial-time algorithms for the selected policy class, using an augmented state that tracks cumulative reward. Integer rewards bound the augmented state space polynomially, while without integrality it can grow exponentially with the horizon.
V. EXACT ALGORITHMS
- The section focuses on exact pseudopolynomial-time algorithms for MV-MDP(Πh,u), after comparisons indicate other policy classes are inferior or have higher apparent complexity.The paper notes that approximate or pseudopolynomial algorithms remain possible despite NP-hardness for Πh,u.Source: §V · p. 10
- The algorithmic approach augments the state with cumulative reward, Xt = (St, Wt).With integer immediate rewards, Wt lies between −KT and KT, giving an augmented state-space size bounded by |S| · (2KT + 1).Source: §V · p. 10
- Without the integrality assumption, the finite augmented state space can grow exponentially with T.The paper treats the integer-reward case separately because its augmented state-space cardinality has a polynomial bound.Source: §V · p. 10
A. State-Action Frequencies
The paper represents policies through state-action frequencies over an augmented state space. For the history-dependent and randomized class, attainable frequency vectors form a polyhedron with a linear-size constraint description in the augmented space, enabling linear-programming feasibility checks.
A. State-Action Frequencies
- A state-action frequency records the probability of being in an augmented state and taking an action at time t; the associated vector collects these frequencies across times, states, and actions.The paper also defines state frequencies as the probabilities of occupying each augmented state at each time.Source: A. State-Action Frequencies · p. 10
- The attainable frequency sets for Πh,u and Πt,s,w,u are equal, and Z(Πh,u) is a polyhedron specified by O(T · |X| · |A|) linear constraints.The paper uses this representation to establish equivalence between the two policy classes.Source: A. State-Action Frequencies · p. 11
- Checking feasibility through the polyhedral representation reduces to linear programming, but the constraint count can be exponential in T because |X| can be exponential.The relevant constraint count is proportional to the augmented state-space cardinality.Source: A. State-Action Frequencies · p. 11
B. Integer Rewards
For integer rewards, the achievable mean and second-moment pairs form a convex set that supports pseudopolynomial algorithms for specified decision problems. The general variance-constrained problem remains difficult, with a pseudopolynomial result for the special case of zero variance.
B. Integer Rewards
- The zero-variance target can be viewed as a reachability game, solvable by backward recursion in time polynomial in the augmented-state count, although the problem is NP-complete.The game asks whether actions can guarantee a total reward k against transitions and rewards with positive probability.Source: B. Integer Rewards · pp. 11, 13, 14
- Both deciding whether a policy attains a specified (Jπ, Vπ) pair and whether Jπ = λ with Vπ ≤ v admit pseudopolynomial-time algorithms for integer rewards.The stated results also rule out polynomial-time algorithms for these problems unless P=NP.Source: B. Integer Rewards · pp. 11–12
- Representing policies by (Jπ, Qπ), where Qπ is the second moment of cumulative reward, yields a polyhedral achievable set that enables pseudopolynomial algorithms for convex-set formulations.The corresponding set of mean-variance pairs need not be convex, limiting this approach for variance-based formulations.Source: B. Integer Rewards · p. 12
- For general variance bounds, the authors report no pseudopolynomial algorithm except for the special case v = 0.They defer an approximation algorithm for general v to the next section.Source: B. Integer Rewards · p. 13
- If a history-based randomized policy achieves zero variance, a deterministic time-, state-, and reward-dependent policy can also achieve zero variance.The argument fixes a realization of the policy’s randomization variables that leaves conditional reward variance zero.Source: B. Integer Rewards · p. 13
- For integer rewards bounded by K, deciding whether any policy has zero reward variance admits a pseudopolynomial-time algorithm.The proof checks possible guaranteed total rewards k in the range |k| ≤ KT.Source: B. Integer Rewards · p. 13
VI. APPROXIMATION ALGORITHMS
The section develops approximations for the mean-variance tradeoff, focusing on the least achievable variance subject to a mean threshold. It presents a weaker approximation notion because uniform approximation is not known to be efficiently computable.
VI. APPROXIMATION ALGORITHMS
- The paper focuses on approximating v*(λ), the least variance achievable when the mean is at least λ, while noting the analogous function λ*(v).If the constraint is infeasible, the stated conventions are v*(λ) = ∞ and λ*(v) = −∞.Source: §VI · p. 14
- The authors do not know how to efficiently compute or uniformly approximate v*(λ) or λ*(v), so they pursue a weaker approximation that is computable in pseudopolynomial time.The weaker approximation algorithm runs in time polynomial in 1/ε and 1/ν as well as pseudopolynomial in the problem parameters.Source: §VI · p. 14
- The proposed (ε, ν)-approximation places the estimated graph within Hausdorff distance ε + ν of the graph of v*(·).The estimate also lies on the (ε + ν)-approximate Pareto boundary of the achievable mean-variance set.Source: §VI · p. 14
- The approximation results treat integer rewards, general rewards, and an alternative algorithm based on set-valued dynamic programming.The general-reward approach follows the integer-reward case, while the alternative is sketched in Section VI-C.Source: §VI · p. 14
A. Integer Rewards
For integer rewards, the section approximates the least variance achievable above a mean threshold using a grid over possible means. The computation uses linear programs on the achievable moment set.
A. Integer Rewards
- The algorithm evaluates grid points across the bounded mean range [−KT, KT] and uses their estimates to approximate v*(λ).The grid spacing δ is chosen in relation to the approximation parameter, with ε = 3δKT in the proof.Source: A. Integer Rewards · p. 15
- Computing the grid estimates requires O(KT/δ) linear programming problems because the achievable mean-second-moment set is a polyhedron.The algorithm estimates the least variance for mean values restricted to each grid interval.Source: A. Integer Rewards · p. 15
- The constructed estimate ˆv(λ) is always an underestimate of v*(λ), and the proof establishes a reverse bound to control its approximation error.The comparison uses monotonicity of v*(·) and the grid interval containing λ.Source: A. Integer Rewards · pp. 15–16
B. General Rewards
For general bounded rational rewards, the paper discretizes rewards and applies the integer-reward approximation algorithm. A coupling argument supports the claim that sufficiently fine discretization keeps the mean-variance tradeoff close.
B. General Rewards
- Rounding rewards down to multiples of δ produces an integer-grid MDP to which the preceding algorithm can be applied.The construction starts with rewards in [−K, K].Source: B. General Rewards · p. 16
- A coupling argument compares the original and discretized MDPs and supports the result that v*(·) changes very little under sufficiently fine discretization.The proposition bounds the Hausdorff distance between their achievable moment sets by a polynomial function of K and T times the discretization scale.Source: B. General Rewards · pp. 16–18
- Theorem 10 gives an algorithm for approximating v*(λ) in time polynomial in |S|, |A|, T, K, 1/ε, and 1/ν.It applies the integer-reward algorithm to the discretized MDP and uses the proposition to transfer the approximation to the original problem.Source: B. General Rewards · p. 18
C. An Exact Algorithm and its Approximation
The section develops an exact set-valued dynamic program for achievable moments, then approximates its polyhedra to control computational growth. The approximation keeps the total error O(ǫ) while limiting each polyhedron to O(1/ǫ) extreme points.
C. An Exact Algorithm and its Approximation
- The section contrasts discretizing the original problem with approximately implementing an exact algorithm, and notes the latter is likely faster in practice.The latter approach requires that approximation errors do not accumulate excessively through the algorithm.Source: C. An Exact Algorithm and its… · pp. 18–19
- The exact dynamic program represents achievable moment pairs at intermediate times and augmented states as sets updated by a set-valued recursion.The sets are polyhedra, but the number of extreme points can make the resulting algorithm exponential in the worst case.Source: C. An Exact Algorithm and its… · pp. 18–19
- The exact recursion is finite to compute using polyhedral representations, but may take exponential time because of the number of extreme points.The recursion's sets are polyhedra, allowing representations by their finitely many extreme points.Source: C. An Exact Algorithm and its… · p. 19
- O(ǫ) total error is achieved with approximating polyhedra having O(1/ǫ) extreme points and O(ǫ/T) error introduced at each stage.The approximation uses the fact that the polyhedra lie in the plane.Source: C. An Exact Algorithm and its… · p. 19
VII. CONCLUSIONS
The conclusion recaps the complexity and algorithmic results for finite-horizon mean-variance MDPs, while identifying boundaries and open questions. It also notes specific variance properties of deterministic and randomized policies and possible extensions to infinite-horizon problems.
VII. CONCLUSIONS
- The paper concludes that mean-variance optimization problems for MDPs are typically NP-hard, while its analysis focuses on finite-horizon problems.The authors state that negative results carry over to infinite-horizon counterparts.Source: §VII · p. 19
- The paper's approximation algorithms can also yield approximation algorithms for infinite-horizon problems.The paper notes that some results can extend to the infinite-horizon discounted case, which is beyond its scope.Source: §VII · p. 19
- The smallest possible variance is attained by a deterministic policy, whereas variance is generally maximized by a randomized policy.In a single-stage example with deterministic rewards 0 and 1, assigning probability 1/2 to each action maximizes variance.Source: §VII · p. 20
- For integer rewards, variance maximization is a quadratic program over the achievable-moments polyhedron and admits a pseudopolynomial-time algorithm.The objective is the concave function q − λ^2 over PMQ.Source: §VII · p. 20
- The authors identify whether hardness extends to specially structured MDPs, including multi-armed bandits, as an open question.They also leave open whether an index-based policy exists for the mean-variance problem.Source: §VII · p. 20
- The paper considers only mean-variance tradeoffs and points to broader risk-aware criteria for multi-stage decision problems as a topic for future theory.The suggested scope includes general monotone convex or concave utility functions and risk constraints.Source: §VII · p. 21