MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a Markov Decision Process with Borel state space $X$ and Borel action space $U$, like the one defined in the book "Stochastic Optimal Control: Discrete-time case" by Bertsekas and Shreve. All the references below to definitions and results are for this book.

I am interested in the case when the cost is $$ J^\pi(x):=\mathsf E^\pi_x\left[\sum_{k=0}^\infty g(x_k)\right]. $$ where $\pi$ is a policy - in general it a sequence of randomized, history-dependent and universally measurable stochastic kernels. The correspondent minimization problem is $$ J^*(x):=\inf_{\pi}J^\pi(x). $$ A policy $\hat\pi$ is called optimal if $J^{\hat\pi} = J^*$.

The Chapter 9 of the book distinguishes two important cases: a positive case $g\geq 0$ [P] and a negative case $g\leq 0$ [N]. Under certain continuity assumptions known as "lower semicontinuous model", Definition 8.7, it holds that an optimal policy can be taken to be stationary and Borel measurable in case of [P].

I wonder, whether under perhaps stronger condition one can obtain existence of optimal (or just $\varepsilon$-optimal) Borel measurable stationary policies for the case [N]. For example, in my case I can assure that $J^*$ is a bounded function.

P.S. Perhaps, the question does not provide all the necessary background, but I hope the linked book helps (there is a pdf on the website). Some background I've given in a question here.

share|cite|improve this question
Are there any conditions that ensure the infinite sum defined above is summable? – Michael Fan Zhang Aug 3 '14 at 5:49
@MichaelFanZhang: it may become unbounded ($-\infty$), but that's in fact important to negative dynamic programming. Also, since $g$ is sign-semidefinite, the sum is always negative so its expectation is well-defined, even though it may be $-\infty$ as well. Did I answer your question? – Ilya Aug 3 '14 at 15:56

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.