PaperlayerView exact revision on arXiv

Source-linked AI summary

Average-Cost Markov Decision Processes with Weakly Continuous Transition Probabilities

Eugene A. Feinberg, Pavlo O. Kasyanov, Nina V. Zadoianchuk

arXiv:1202.4122v1math.OC

TL;DR

The paper addresses when stationary optimal policies exist for average-cost MDPs with weakly continuous transitions, unbounded costs, and noncompact action sets. It develops sufficient conditions, optimality inequalities, and discount-based approximations, establishing stationary average-cost optimal policies and compact approximating action sets under the stated assumptions.

  • Problem

    The paper asks when stationary optimal policies exist for average-cost MDPs with Borel spaces, weakly continuous transitions, unbounded costs, and noncompact action sets.

  • Method

    It develops general existence conditions, an optimality-inequality criterion, and approximations of average-cost optimal actions by discount-optimal actions.

  • Results

    The results establish stationary discount- and average-cost optimal policies and show that selected discount-optimal actions form nonempty compact sets supporting stationary average-cost optimal policies.

  • Takeaways & Limitations

    The conditions broaden applicability beyond assumptions requiring inf-compact costs in both state and action, including bounded-cost cases with unbounded state spaces.

  • Takeaways & Limitations

    The conclusions rely on assumptions such as lower semicontinuity, weak continuity, and a boundness condition on relative discounted values.

Abstract

from arXiv · show

This paper presents sufficient conditions for the existence of stationary optimal policies for average-cost Markov Decision Processes with Borel state and action sets and with weakly continuous transition probabilities. The one-step cost functions may be unbounded, and action sets may be noncompact. The main contributions of this paper are: (i) general sufficient conditions for the existence of stationary discount-optimal and average-cost optimal policies and descriptions of properties of value functions and sets of optimal actions, (ii) a sufficient condition for the average-cost optimality of a stationary policy in the form of optimality inequalities, and (iii) approximations of average-cost optimal actions by discount-optimal actions.

1 Introduction

The paper develops conditions for stationary optimal policies in average-cost MDPs with weakly continuous transitions, unbounded costs, and potentially noncompact action sets. It also addresses optimality inequalities and approximation of average-cost optimal actions by discount-optimal actions.

  • 1 Introduction: The paper gives sufficient conditions for stationary discount-optimal and average-cost optimal policies in Borel MDPs with weakly continuous transitions.The conditions allow unbounded one-step costs and noncompact action sets.
  • 1 Introduction: Optimality inequalities provide a sufficient condition for the average-cost optimality of a stationary policy.This extends the tools available when optimality equations are inadequate for unbounded-cost problems.
  • 1 Introduction: The framework uses weak continuity, which can apply under more general demand distributions in inventory models than setwise continuity.The paper contrasts weak convergence with stronger setwise convergence in this application context.
  • 1 Introduction: The paper weakens a boundness condition on relative discounted values while retaining results for weakly continuous transitions and possibly noncompact actions.Its original goal was to remove the local boundedness condition used in earlier results.
  • 1 Introduction: Assumption (W*) covers bounded and unbounded costs with noncompact action sets, beyond more restrictive inf-compactness requirements in both state and action.The paper notes that inf-compactness in the state argument can exclude bounded-cost models on unbounded state spaces.
  • 1 Introduction: Assumption (W*) is presented as weaker than earlier compactness, continuity, and two-argument inf-compactness assumptions, while addressing pathological lower-semicontinuous-cost cases.The cited pathology shows that inf-compactness only in the action variable may be insufficient.

2 Model Description

The model is a discrete-time MDP with Borel state and action spaces, state-dependent feasible actions, measurable costs, and a transition kernel. Policies may use randomized history-dependent decision rules, while stationary policies select measurable feasible actions from each state.

  • 2 Model Description: At each epoch, the process observes a state, selects a feasible action, incurs one-step cost, and transitions according to q(·|x,a).The state and action spaces are Borel subsets of Polish spaces, and the cost is bounded below and measurable on the feasible graph.
  • 2 Model Description: A policy is a sequence of randomized decision rules based on complete histories, with each rule concentrated on the actions feasible in the current state.Nonrandomized policies concentrate each decision rule at a single action.
  • 2 Model Description: Stationary policies are measurable mappings φ:X→A satisfying φ(x)∈A(x) for every state.The set of stationary policies is denoted by F.
  • 2 Model Description: The finite- and infinite-horizon discounted costs are defined from the expected accumulated one-step costs under a policy.The infinite-horizon discounted criterion uses α∈[0,1), while α=1 is used for the undiscounted finite-horizon notation.
  • 2 Model Description: A policy is discount-optimal when it attains the optimal discounted value and average-cost optimal when it attains the optimal average-cost value for every initial state.Finite-horizon optimality can be characterized through recursively defined optimality equations and corresponding Markov decision rules.
  • 2 Model Description: The discounted value function satisfies a discounted cost optimality equation, and a stationary policy is discount-optimal exactly when it satisfies the associated minimizing condition.The supplied passage introduces the DCOE and its stationary-policy characterization.

3 General Assumptions and Auxiliary Results

This section introduces weak-continuity assumptions and establishes auxiliary measurability, compactness, and lower-semicontinuity properties needed to construct stationary policies and optimal actions. Under Assumption (W*), the paper derives measurable optimal-action sets and a sufficient condition for stationary average-cost optimality.

  • Stationary optimality: Theorem 3.1 states that if a nonnegative measurable function and a stationary policy satisfy the required inequality, a measurable selector choosing from the optimal-action sets is available and yields a stationary average-cost optimal policy.The construction uses an inequality-based verification argument rather than requiring optimality equations.
  • Assumptions: Assumption (W*) requires lower-semicontinuous bounded-below costs and ensures that bounded-cost action sequences over converging states have limit points in the limiting feasible action set.This condition is weaker than requiring the one-step cost to be inf-compact in both state and action arguments.
  • Assumptions: Assumptions (W) and (Wu) each imply the more general Assumption (W*), which accommodates bounded or unbounded costs and possibly noncompact action sets.The implication from (W) is obtained through upper-semicontinuity and compact actions, while (Wu) uses inf-compactness of the cost on the graph.
  • Auxiliary results: Under Assumption (W*), one-step minimization over A(x) attains its minimum, and the resulting optimal-action graph is Borel with compact sections whenever the value is finite.The minimizer correspondence is nonempty; when the value is infinite, the optimal-action set equals the full feasible action set.

4 Expected Total Discounted Costs

Under Assumption (W∗), the paper establishes standard discounted-MDP properties, including lower semi-continuity and monotone convergence of value functions, measurable compact optimal-action sets, and stationary discount-optimal policies.

  • Discounted-cost results: Assumption (W∗) yields stationary discount-optimal policies and strengthens prior results without requiring holding costs to increase to infinity in inventory and queuing applications.The theorem also characterizes stationary optimal policies through the sets Aα(x).
  • Value functions: The value functions vn,α and vα are lower semi-continuous, and vn,α(x) increases to vα(x) for every state.These properties hold for finite-horizon iterates and the infinite-horizon discounted value function.
  • Optimal actions: The finite-horizon optimal-action sets have Borel graphs and are compact whenever vn+1,α(x) is finite; when it is infinite, they equal A(x).Selecting actions from these sets yields N-horizon optimal Markov policies.
  • Optimal actions: The infinite-horizon optimal-action sets Aα(x) have Borel graphs and are compact whenever vα(x) is finite, while equaling A(x) when vα(x) is infinite.A stationary policy is discount-optimal exactly when it selects from Aα(x) at every state.
  • Value functions: The conclusions remain valid for costs bounded below by shifting the cost function by a constant and transforming the corresponding value functions.The shift preserves the stated discounted-value properties.

5 Average Costs Per Unit Time

Under Assumptions (W∗) and (B), the paper derives average-cost optimality inequalities, constructs stationary average-cost optimal policies, and shows that suitable discount-optimal actions can approximate average-cost optimal actions.

  • Assumptions: Assumption (B)(ii) is weaker than Schäl’s boundedness condition, while being equivalent to another formulation under Assumption (G).The paper contrasts its boundedness requirement with prior assumptions used for average-cost results.
  • Average-cost optimality: Theorem 5.2 establishes average-cost optimality inequalities and stationary optimal policies under the weaker boundedness Assumption (B) together with Assumption (W∗).It also provides lower semi-continuity of u, compact optimal-action sets, and measurable stationary selectors.
  • Value functions: The function u defined from relative discounted values is lower semi-continuous, and it becomes inf-compact when Assumption (Wu) also holds.The corresponding discounted relative-value functions uα are lower semi-continuous under (W∗) and inf-compact under (Wu) and (B).
  • Optimal actions: The sets A∗(x) are nonempty and compact with Borel graph, and any stationary policy selecting from them satisfies the average-cost optimality inequalities and is average-cost optimal.A stationary selector exists because the action sets have the required measurable structure.
  • Discount-to-average approximation: Theorem 5.6 and its corollaries retain these conclusions while connecting average-cost optimal actions with limits or approximations of discount-optimal actions as α increases to 1.The paper also states that the conclusions remain valid using the alternative function ũ.

6 Approximation of Average Cost Optimal Strategies by α-discount Optimal Strategies

Under Assumptions (W*) and (B), the paper establishes stationary average-cost optimal policies and shows that average-cost optimal actions can be approximated by discount-optimal actions as α increases to 1.

  • 6 Approximation of Average Cost Optimal Strategies by α-discount Optimal Strategies: The approximation result follows by analyzing upper topological limits of the graphs of discount-optimal action sets.The section considers the upper topological limit of the family {Gr(A_α)} and uses convergent state-action pairs to obtain the approximation.
  • 6 Approximation of Average Cost Optimal Strategies by α-discount Optimal Strategies: Theorem 6.1 establishes that A_app has a Borel graph, nonempty compact action sets, and a stationary policy selecting from A_app is average-cost optimal.The theorem places A_app inside A* and guarantees that any stationary policy selecting A_app(x) is optimal.
  • 6 Approximation of Average Cost Optimal Strategies by α-discount Optimal Strategies: Average-cost optimal actions are limits of α-discount optimal actions evaluated at nearby states as α increases to 1.For each state x, there are α_n(x) increasing to 1, y_n(x) converging to x, and a_n(x) in A_αn(x)(y_n(x)) converging to the selected average-cost action.
  • 6 Approximation of Average Cost Optimal Strategies by α-discount Optimal Strategies: The same conclusions remain valid when the function u in the relevant inequality is replaced by the alternative function ũ defined in (5.18).This replacement preserves both Theorem 6.1 and Corollary 6.2.
  • 6 Approximation of Average Cost Optimal Strategies by α-discount Optimal Strategies: Under Assumptions (G) and (W_u), all sets X_α are contained in one compact subset of the state space.Theorem 6.3 supplies a compact K such that X_α ⊆ K for every α in [0,1).

7 Illustrative Example

The illustrative example concerns an MDP on the real line with weakly continuous transitions arising from arbitrary iid noise with zero mean and finite variance.

  • 7 Illustrative Example: The noise variables are iid with zero mean, finite variance, and, in the density case, continuous density.The example specifies these distributional conditions for the random variables ξ_n.
  • 7 Illustrative Example: The example is an MDP with X = A = R whose transition probabilities may be weakly continuous even when the noise lacks a density.With a continuous density, the transition probabilities are setwise continuous; without one, weak continuity is retained.
  • 7 Illustrative Example: For arbitrary iid noise with zero mean and finite variance, the problem satisfies one of the paper’s assumptions despite the possible loss of setwise continuity.The passage connects this example to the paper’s framework for weakly continuous transition probabilities.

A Proof of Lemma 3.5

The appendix proof establishes a lower-semicontinuity result by first treating uniformly bounded functions and then extending the argument through truncation and Fatou’s lemma.

  • A Proof of Lemma 3.5: The proof begins with the case of measurable functions uniformly bounded above by a finite constant.It assumes h_n(s) ≤ K for every n and s before handling nonnegative functions more generally.
  • A Proof of Lemma 3.5: The proof verifies lower semicontinuity through open superlevel sets and then invokes Fatou’s lemma to complete the limiting argument.The passages identify open sets generated by the functions and explicitly apply Fatou’s lemma.
  • A Proof of Lemma 3.5: Nonnegative functions are truncated using h_n^λ(s) = min{h_n(s), λ} to reduce the argument to uniformly bounded functions.The truncation parameter λ provides bounded approximations to the original sequence.
Loading 1202.4122v1…