0
$\begingroup$

I have recently learned some things about Reinforcement Learning and did now think for myself about Markov Reward Processes (MRPs), without engaging a lot with the literature. I have almost no background in probability theory, which may explain the naivety of my question.

Usually in an MRP one uses discounting to make the mathematics "finite". I tried to generalize this in the following way: Instead of discounting, I do not discount, but I regard one state as "attracting" in the sense that from every state there is a path to the attracting state. The attracting state itself is also absorbing, so no arrow leaves it, except an arrow pointing to itself. And furthermore, the reward for the state transition from the attracting state to itself is always $0$.

Question 1: Is there always a well-defined, finite expected value for the sum of rewards starting in a specific state?

Question 2: Does the term "attracting state" also exist in the literature, and how is it called there?

What follows now just makes the description thus far more explicit: I consider an MRP $(S, R, P)$, where $S =\{s_1, \dots s_{n+1}\}$ is the set of states, $R = \{r_1, \dots, r_{n+1}\}$ is the set of rewards, where $r_i$ is the reward received for leaving state $s_i$, and $P \in \mathbb{R^{(n+1) \times (n+1)}}$ is the state transition probability matrix, with entries $p_{ij} = \text{Pr}(X_{n+1} = s_{j}\ | \ X_{n} = s_i )$.

Furthermore, the state $s_{n+1}$ is attracting, which means the following:

(i) For all $i$ there is a sequence $i = k_1, \dots, k_s = n + 1$ such that $\prod_{j = 1}^{s-1}p_{k_j,k_{j+1}} > 0$.

(ii) $p_{n+1,n+1} = 1$ and $p_{n+1,j} = 0$ for all $j \neq n+1$.

(iii) $r_{n+1} = 0$.

It is easy to see that this setting is strictly more general than the setting of MRPs with discounting: Assuming we have an MRP with discounting factor $\gamma$, we can build an MRP with attracting state from it by adding one additional state such that every other state reaches the new state with probability $1-\gamma$ in every step (and by rescaling the other probabilities accordingly).

The value of state $i$ is defined as

$$V(i) = \text{E}\left[\sum_{j = 0}^{\infty} R_j \ | \ X_0 = s_i\right],$$

where $R_j$ is the reward received in time-step $j$ for leaving state $X_j$.

I believe that this expected value is always a finite, well-defined number, but I am not quite able to prove it. What I was able to show is the following: Assuming the expected value exists (and is a real number) then we can find it as usual by applying Dynamic programming with help of the Bellmann Equation. The Bellmann operator is not a contraction in this case, but if we compose it often with itself then we can build a contraction from it and the usual prove, using the Banach fix-point theorem, leads to a solution. But this whole proof only gives a procedure for computing the expected values assuming they exist, and this is the place where I do not quite know how to do it. Do you have any ideas?

It may be that the answer will already be clear as soon as I understand the proof fully in the discounting case. Unfortunately, the only text about that that I am aware of, Algorithms for Reinforcement Learning, does also not seem to resolve my question. (Although in that case, the expectation is defined over values which are all finite. In my case, there can be a probability of $0$ to have infinite future reward or even undefined future reward, for example if the sequence of rewards is something like $-1, 1, -1, 1, -1, 1, ...$).

Best regards

Leon

$\endgroup$
  • $\begingroup$ Answer to Question 2: these are normally (in what I’ve read) called “absorbing states” (see this Wikipedia article, for example). Also, the book by Puterman on Markov Decision Processes might be a helpful reference (it was written before reinforcement learning was really “hot”, but has nice coverage of theory. It’s about MDPs, not MRPs, but helpful if you’re interested) $\endgroup$ – David M. Aug 2 '18 at 23:21
  • $\begingroup$ Also, if you think about the case where $R_i=1$ for all transient states (and $R_i=0$ for absorbing states, as you suggest), then the total expected reward is just the expected number of times you visit each transient state. This value is well-defined, finite and easy to compute (see the Wikipedia article in the previous comment). From this, you might be able to think of a way to build the general proof. $\endgroup$ – David M. Aug 3 '18 at 0:07
  • $\begingroup$ Hello @DavidM., thanks for telling me their name (absorbing state in an absorbing markov chain). I think the main problem is not the intuition or the proof strategy. For example, I found the formula for the inverse of (I_t - Q) in your linked article actually myself. My problem is that I am computing the expected value of something which seems not quite well defined to me, since it is actually possible that the markov chain never reaches the absorbing state. So, how does one (formally) deal with these arising infinities? $\endgroup$ – Leon Lang Aug 10 '18 at 23:34
  • $\begingroup$ I see. I don't have a complete answer at the moment, but I think if you try to prove the simple case in my previous comment, you might be able to prove the more general case. Not sure though. $\endgroup$ – David M. Aug 11 '18 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.