Notes

Markov Chain (MC) A Bayesian Network is a kind of PGM that uses a directed (acyclic) graph to represent a factorized probability distribution and associated conditional independence over a set of variables.

Definition: A state $S_{t}$ is Markov if and only if:

$$P\left( S_{t + 1} \middle| S_{t} \right) = P\left( S_{t + 1} \middle| S_{1:t} \right)$$

where $s_{t}$ is the current state and $s_{t + 1}$ is the successor state.

The state captures all relevant information from the history. Once the state is known, the history may be thrown away. This means that the state is a sufficient statistic of the future.

The state transition matrix P defines transition probabilities from all states $m = s_{t}$ to all successor states $n = s_{t + 1}$: (Left) An example Markov Chain showing all state transition probabilities next to its node. (Right) The corresponding state transition matrix and results of a sampling procedure applied to this Markov chain. Be aware that this is not a PGM, the nodes are not random variables.

Markov Reward Process (MRP) A Markov reward process is a stochastic process which extends a Markov chain by adding a reward rate to each state. Definition: A Markov Reward Process is a tuple $(S,P,R,\gamma)$ where S is a finite set of states, P is a state transition probability matrix $P_{t,t + 1} = P\left( S_{t + 1} \middle| S_{t} \right)$, $R = \mathbb{E}\left\lbrack R_{t + 1} \middle| S_{t} = s \right\rbrack$ is a reward function and $\gamma$ is a discount in the interval (0,1).

Facts:

• Mathematically convenient to discount rewards. It avoids infinite returns in cyclic Markov processes.
• Uncertainty about the future may not be fully represented.
• If the reward is financial, immediate rewards may earn more interest than delayed rewards.
• Animal/Human behavior shows preference for immediate rewards.
• It is sometimes possible to use un-discounted Markov reward processes (i.e., $\gamma = 1$), e.g., if all sequences terminate.

We call $G_{t}$ the return which is the total discounted reward from time step t onward.

$$G_{t} = R_{t + 1} + \ \gamma\ R_{t + 2} + \ldots = \sum_{k = 0}^{\infty}{\gamma^{k}R_{t + k + 1}}$$

If we just look at $G_{t}$ we must assume that we know the chain of events that lead to the specific rewards R, however the MRP is a stochastic process. Therefore we may compute the conditional value function given that we know where we start ($s_{t})$. We have seen this function before in the RL chapter:

$$v_{s_{t}}\mathbb{= E}\left\lbrack R_{t + 1} + \gamma R_{t + 2} + \gamma^{2}R_{t + 3} + \ldots \middle| S_{t} = s \right\rbrack$$

which is just

$$v_{s_{t}}\mathbb{= E}\left\lbrack G_{t} \middle| S_{t} = s_{t} \right\rbrack$$

Hence, the state value function $v(s)$ of an MRP is the expected return starting from state s. It gives the long-term value of state s.

Markov Decision Process (MDP) Markov Decision Process (MDP) is a Markov reward process with decisions (actions that we can take). It is still an environment in which all states are Markov.

Definition: A Markov Reward Process is a tuple $(S,A,P,R,\gamma)$ where S is a finite set of states, A is a finite set of actions, P is a state transition probability matrix $P_{t,t + 1} = P\left( S_{t + 1} \middle| S_{t},A_{t} \right)$, $R = \mathbb{E}\left\lbrack R_{t + 1} \middle| S_{t} = s,A_{t} = a \right\rbrack$ is a reward function and $\gamma$ is a discount in the interval (0,1).

Markov Decision Processes formally describe an environment for Reinforcement Learning where the environment is fully observable. Almost all RL problems can be formalized as MDPs.

• Partially observable problems can be converted into MDPs.
• One Armed Bandits are MDPs with one state.

The MC seen before extended to be a MRP is here extended again to be an MDP. However, we should be careful with the comparisons. In the MRP, our agent was guided purely by randomness and we had no choice. Now, the agent is able to directly influence its path. Note that some of the transitions are deterministic. For example, if we quit Facebook, we are for sure back to studying, however if were in the pub, we might be too drunk and randomness influences the outcome.

One can see that we are very close now to what we introduced in the RL section, however, one key piece is missing. Given that we have choice as an agent now, how do we know the optimal behavior?