Sequential Decision Making

No notes for first half of video

The action $a^{\ast }$ which a rational agent should choose is that which maximises the agent’s utility. In other words, the agent should pick:

Where $s_a$ is the state obtained by choosing action $a$ and $u(s_a)$ is the utility of that state. The problem is that in any realistic situation, the resulting state is probabilistic. Instead we have to calculate the expected utility of each action and make choice based on that.

In other words, for each action $a$ with a set of outcomes $s_a$, the agent should calculate:

and pick the best.

Example: decision between $E[(a_1)]$ and $E[u(a_2)]$.

We are working with stochastic actions whereby an action has several possible outcomes, and we don’t know which will happen in advance.

Policies

Maximin

Maximin is a decision rule that dictates that you should choose the least-bad option for a worst case (maximum loss) scenario.

$$a^{\ast }=\text{arg }\underset{a\in A}{\max }\{\underset{s^{\prime }\in s_a}{\min }u(s^{\prime })\}$$Link to original

Maximax

Maximax is optimistic risk-seeker, which will ignore all bad possible outcomes and just focus on the best possible outcome.

$$a^{\ast }=\text{arg }\underset{a\in A}{\max }\{\underset{s^{\prime }\in s_a}{\max }u(s^{\prime })\}$$Link to original

Transition Model

We can write a transition model to describe these actions. Since the actions are stochastic, the model looks like:

$$P(s^{\prime }|s,a)$$

Where $a$ is the action that takes the agent from $s$ to $s^{\prime }$.

Transitions are assumed to be first order Markovian, that is, they only depend on the current and next states. So we can write a large set of probability tables that describe all possible actions executed in all possible states.

Link to original

Example

The reward for non-terminal states is $-0.04$. We assume the utility of a run is the sum of utility of states, therefore $-0.04$ is an incentive to take fewer steps to get to the terminal state.

This gives us the policy:

Here are different optimal policies for values of $R(s)$:

The problem the agent faces here is a

Markov Decision Process

A Markov Decision Process is the process of looking at actions influencing state transitions. It is a sequential decision making problem for a fully observable yet stochastic environment.

Markov Chain holds, but now with probability of actions between states and rewards for action execution. This is reliant on two principles:

• Assume Markov property holds for action transitions.
• Probability distributions are stationary and don’t change.

We encode a reward for each state. Total utility of the agent is the sum of all rewards from all states visited.

A negative reward incentives optimality.

The MDP components for all states $s\in S$:

• transition model: $T(s,a,s^{\prime })$
• initial state of the problem: $s_0$
• reward function for a given state: $R(s)$

The MDP solution is not a plan of actions. The MDP solution is a policy $\pi$ which denotes the action $\pi (s)$ that should be taken for any state $s\in S$. The optimal policy (${\pi }^{\ast }$) will yield the highest expected utility in any given situation.

Link to original

Optimal Policies

So far we’ve assumed utilities are summed along a run, but it’s not the only approach.

• In general, we need to compute $U_r([s_0,s_1,\dots ,s_n])$ for general $U_r(.)$, this is the utility of the run.
• Before, $U_r(.)$ was just the sum of rewards in every state.
• We can consider either finite or infinite ‘horizons’ / games. For us, dealing with infinite horizons is easier so that’s what we will use.

We have to also consider whether the utilities are stationary: that is whether a state always has the same value, it could change after we visit it for example. We assume utilities are stationary.

With stationary utilities, there are two ways to establish $U_r([s_0,s_1,\dots ,s_n])$ from $R(s)$.

• Additive rewards: $U_r([s_0,s_1,\dots ,s_n])=R(s_0)+R(s_1)+\dots +R(s_n)$
• Discounted rewards: $U_r([s_0,s_1,\dots ,s_n])=R(s_0)+\gamma R(s_1)+\dots +{\gamma }^{n}R(s_n)$ where the discount factor $\gamma$ is a number between $0$ and $1$

The discount factor models the preference of the agent for current over future rewards.

There is an issue with infinite sequences with additive, undiscounted rewards.

The utility of the policy will be unbounded, hence $\infty$ or $-\infty$. This is problematic when we want to compare policies.

We have some solutions to this problem:

• Proper policies
• Average reward
• Discounted rewards

Proper Policies

Proper Policy

A proper policy always ends up in a terminal state eventually, thus have a finite expected utility.

Link to original

Average Reward

Average Reward (policies)

We can compute the average reward per time step. Even for an infinite policy, this will usually be finite.

Link to original

Discounted Rewards

Discounted Rewards (policies)

Assume $0\le \gamma <1$ and rewards are bounded by $R_{\text{max}}$. With discounted rewards, the utility of an infinite sequence is finite:

$$\begin{array}{rl}{U}_r([s_0,s_1,\dots ,s_n])& =\sum _{t=0}^n{\gamma }^{t}R(s_t)\\ & \le \sum _{t=0}^{\infty }{\gamma }^{t}R(s_t)\\ & \le \sum _{t=0}^{\infty }{\gamma }^t{R}_{\text{max}}\\ & \le \frac{R_{\text{max}}}{(1-\gamma )}\end{array}$$

We can compare policies by computing their expected values. The expected utility of executing $\pi$ starting in $s$ is given by:

$$U^{\pi }(s)=E\left[\begin{array}{c}{\sum }_{t=0}^{\infty }{\gamma }^{t}R(s_t)\end{array}\right]$$

Where $S_t$ is the state the agent gets to at time $t$.

$S_t$ is a random variable and we compute the probability of all its values by looking at all the runs which end up there after $t$ steps.

The optimal policy is then:

$${\pi }^{\ast }=\text{arg }\underset{\pi }{\max }{U}^{\pi }(s)$$

This is independent of the state the agent starts in.

Link to original

Bellman and Value Iteration

3. Value Iteration

Solving the MDP

We wish to find an optimal policy (${\pi }^{\ast }$) for the problem that is:

• complete: covers all states
• optional: gives the best action for state $s$
• stationary: actions dependent only on current state
• proper: guaranteed to reach terminal state

Our policy should yield an expected utility for a given state following a policy $U^{\pi }(s)$

$$U^{\pi }(s)=E\left[\begin{array}{c}{\sum }_{t=0}^{\infty }{\gamma }^{t}R(St)\end{array}\right]$$

Consider ${\pi }^{\ast }(s)$ for the problem as $U^{\pi }(s)$: it is the expected sum of discounted rewards if the agent is running the optimal policy.

Hence we now have two ways of acknowledging rewards in the problem space:

• $R(s)$: the short-term reward when reaching a given state
• $U(s)$: the long-term reward of passing through $s$ on the way to the goal

Meaning that our optimal solution is selecting the action with best expected utility:

$${\pi }^{\ast }(s)=\underset{a\in A(s)}{\mathrm{argmax}}\sum _{s^{\prime }}P(s^{\prime }|s,a)U(s^{\prime })$$

$R(s)=-0.04$	$U(s)\to R(s)=-0.04,\gamma =1$

Calculating Optimal Policy

We need to calculate the utility of each state so we can derive the optimal action. Utility calculation considers all discounted rewards over time, but future rewards are derived from states with other utility values. Hence we can calculate a utility as the immediate reward plus the expected utility of the successor, assuming optimal action selection.

Bellman Equation

The Bellman equation:

$$U(s)=R(s)+\gamma \underset{a\in A(s)}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)U(s^{\prime })$$Link to original

For the example given prior, take for example we want to know the value of $U(1,1)$:

$$U(1,1)=-0.04+\gamma \cdot \underset{a\in A(1,1)}{\max }\{\begin{array}{l}0.8U(1,2)+0.1U(2,1)+0.1U(1,1)\\ 0.9U(1,1)+0.1U(1,2)\\ 0.9U(1,1)+0.1U(2,1)\\ 0.8U(2,1)+0.1U(1,2)+0.1U(1,1)\end{array}$$

Value Iteration Algorithm

To create the value iteration algorithm, we use the Bellman update equation:

$$U_{i+1}(s)=R(s)+\gamma \underset{a\in A(s)}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)U(s^{\prime })$$

We initialise $U(s)=0\forall s\in S$ then update $U(s)$ for all states in the problem. As time $t\to \infty$, the utility values will reach an equilibrium and stabilise.

Value Iteration Psuedocode

Link to original

Policy Iteration

Policy Iteration

Rather than compute optimal utility values, policy iteration looks through the space of possible policies. We start from some initial policy ${\pi }_0$ and do:

1. Policy evaluation: given a policy ${\pi }_i$, calculate $U_i(s)$ Given a policy, the choice of action in a given state is fixed so compute for every state:

$$U_i(s)=R(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,{\pi }_i(s))U_i(s^{\prime })$$

Abstract

We have lots of simultaneous equations again, but this is now linear! (no max)

2. Policy improvement: given $U_i(s)$, compute ${\pi }_{i+1}$ Calculate a new policy ${\pi }_{i+1}$ by applying:

$${\pi }_{i+1}(s)=\text{arg }\underset{a\in A(s)}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)U_i(s^{\prime })$$

for each state $s$. (we do a one-step MEU lookahead)

We perform both of these until convergence, the iteration will terminate when there is no improvement in utility from one iteration to the next. (at this point the utility $U_i$ is a fixed point of the Bellman update and so ${\pi }_i$ must be optimal)

Link to original

Issue with policy evaluation stage

If we have $n$ states, we have $n$ linear equations with $n$ unknowns. The solution is in $O(n^3))$ (there is also an impractical solution with $O(n^{2.376})$). For large $n$, we will run into problems. So we need an approximate solution.

Approximate Policy Evaluation

Approximate Policy Evaluation

Run a simplified value iteration. The policy is fixed, so we know what action to do in each state. Repeat the following a fixed number of times:

$$U_{i+1}(s)\leftarrow R(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,{\pi }_i(s))U_i(s^{\prime })$$Link to original

Modified policy iteration using approximate evaluation

Policy Iteration (using approximate evaluation)

Hence our modified policy iteration is, repeated until convergence:

1. Approximate policy evaluation: repeat fixed number of times $U_{i+1}(s)\leftarrow R(s)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,{\pi }_i(s))U_i(s^{\prime })$
2. Policy improvement: for every state $s$: ${\pi }_{i+1}(s)=\text{arg }\underset{a\in A(s)}{\max }{\sum }_{s^{\prime }}P(s^{\prime }|s,a)U_i(s^{\prime })$

Link to original

This is often more efficient than policy iteration or value iteration.

This is an approximate solution, which may not always converge.

However, one could use the approximate values found here and then continue to use value iteration or policy iteration going forwards.