Skip to main content
added 358 characters in body
Source Link
SBF
  • 1.7k
  • 11
  • 30

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] $$$$ \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.

Edited:

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.

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] $$ 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.

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.

Edited:

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.

Source Link
SBF
  • 1.7k
  • 11
  • 30

Maximal probability of "infinitely often" over MDP

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] $$ 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.