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

Let us consider a Markov Decision Process (MDP) with a Borel state space $X$. Often, the optimization problems over MDP involve optimization of some objectives dependent on the reward function $$ r:X\to\Bbb R $$ for example the discounted cost or the average cost $$ \mathsf E^\pi\left[\sum_{k=0}^\infty \beta^kr(x_k)\right], \quad \limsup_{n\to\infty}\frac1n \mathsf E^\pi\left[\sum_{k=0}^n r(x_k)\right]. $$ where $\pi$ here denotes a control policy. I am looking into optimization of $$ \mathsf E^\pi\left[\limsup_{n\to\infty} r(x_n)\right] \tag{1} $$ and in particular at the case when $r(x) = 1_A(x)$, so that the objective becomes $$ \mathsf P^\pi\left[x_n\in A\text{ infinitely often}\right]. $$

There is a vast amount of literature on this latter problem for the case when $X$ and the control space are finite, especially in the computer science community. I am however interested in the case when both $X$ and the control space are general Borel spaces, but unfortunately so far my literature search was not very successful.

It would be nice if you can advise me some literature on this topic.


Apparently, $(1)$ allows for an equivalent form $$ \mathsf E^\pi\left[\limsup_{n\to\infty} r(x_n)\right] = \limsup_\tau\mathsf E^\pi\left[r(x_\tau)\right] $$ where the latter $\limsup_\tau$ is taken over directed set of stopping times, and thus of course different from $\limsup_n\mathsf E^\pi\left[r(x_n)\right]$ in general.

share|cite|improve this question

Just for the sake of the question having an answer, the following paper by A. Maitra and W. Sudderth gives a very nice characterization of the value function for the i.o. event in the framework of gambling. They provide both the fixpoint equation, and the inductive way of obtaining the value function.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.