We want to find the optimal policy \(\pi\) for a finite markov decision process (MDP)

We have a feedback loop as such

• Agent \(\xrightarrow{S_t, A_t}\) Environment \(\xrightarrow{S_{t+1}, R_{t+1}}\) Agent \(\xrightarrow{\ldots} \ldots\)

In particular, we may define policies \(\pi(a \mid s)\) that determine what actions the agent takes at each state.

Then, we will try and maximize the discounted return \(G^{(\pi)}_t = \sum_{k=t+1}^T \gamma^{k - {t + 1}} R_k\). Note that because these are probabilistic policies, we want \(\mathrm{max}_\pi \mathbb{E}[G^{(\pi)}_t]\).

Finally, it is useful to define the value functions that we will be working with

• State Value \(v_\pi(s) = \mathbb{E}[G^{(\pi)}_t \mid S_t = s]\)
• Action Value \(v_\pi(s, a) = \mathbb{E}[G^{(\pi)}_t \mid S_t = s, A_t = a]\)

We shall simulate one possible example of a (deterministic) Markov Decision Process.

Suppose we have \(\mathcal{S} = \{1, 2, 3\}\), \(\mathcal{A} = \{1, 2\}\). Further, suppose our reward function \(p(R_t = r \mid S_t = s, A_t = a)\) is as follows

• \(p(-1 \mid s, a) = \frac{s + a}{5}\)
• \(p(+1 \mid s, a) = 1 - p(-1 \mid s, a)\)

And our state transitions are

• \(s \xrightarrow{a} s + 1 \ (\mathrm{mod} \ 3)\)
• \(s \xrightarrow{b} s - 1 \ (\mathrm{mod} \ 3)\)

We can set our starting distibution to be uniform. Finally, we define the terminal state to occur after \(N\) time steps.

For example, we may choose a deterministic policy \(\pi(1 \mid s) = 1\), and \(\pi(2 \mid s) = 0\).

• \(1 \xrightarrow{1} 2 \xrightarrow{1} 3 \xrightarrow{1} 1 \xrightarrow{1} \ldots \xrightarrow{1} 1 + N \ (\mathrm{mod} \ 3)\)
• \(2 \xrightarrow{1} \ldots \xrightarrow{1} 2 + N \ (\mathrm{mod} \ 3)\)
• \(3 \xrightarrow{1} \ldots \xrightarrow{1} N \ (\mathrm{mod} \ 3)\)

each with probability \(\frac{1}{3}\).

Home 1 2 3 4(b) 5 6 Next