Machine Learning

Markov Decision Process

The mathematical model used for reinforcement learning is a Markov decision process. A MDP is defined by states $S$, actions $A$, rewards $R\subseteq\bold{R}$, and transition probabilities, $$p(s',r'|s,a) = P(S_{t+1} = s', R_{t+1} = r'\mid S_t = s, A_t = a),$$ the probability of moving to state $s'$ and receive reward $r'$ given you are in state $s$ and take action $a$ at time $t$. Some models specify $A_s\subseteq A$, for $s\in S$, the set of possible actions when in state $s$.

At time $t$ in state $s$ an action $a$ results in a new state $s'$ and reward $r'$ at time $t+1$ with probability $p(s',r'|s,a)$. The process is called Markov because the probablity does not depend on $t$. There is no reason it couldn’t but that would make it harder to find your keys in a dark alley.

In the multi-armed bandit problem there is only one state: the set of machines to play. The action is which machine to play. This results in the reward $r'$ with probability $p(r'|a)$ after you drop a dollar in machine $a$. The next round still has the same set of machines available for play.

A policy $π(a|s)$ specifies the probability of taking action $a$ given you are in state $s$. This results in a sequence of random variables describing possible future states and rewards: $S_{t + k}$, $R_{t + k}$, $k > 0$, given $S_t = s$. A more clever approach might look at the history of the results of prior actions, but we are stumbling under Markov’s steet light for now.

Reinforcement learning is the study of how to find the optimal policy, for some definition of optimal.

A gain function is any function of future rewards, $$G_t = g_t(R_{t+1}, R_{t+2}, \ldots).$$ Common choices are are average future rewards over a horizon $k$ $$G_t = (1/k) \sum_{j=1}^k R_{t + j}$$ and exponential discounting of future rewards $$G_t = \sum_{k > 0} γ^k R_{t + k},$$ where $0<γ<1$ is the discount factor.

The state-value function for policy $π$ is $V_π(s) = E[G_t\mid S_t = s]$, the expected gain from the policy. Reinforcement learning assumes you want a policy that maximizes this. Nobel prizes have been won by people who have demonstrated sure rewards seem to be preferred over uncertain rewards having larger expected value. People also seem to prefer uncertain losses over certain loss. (Reflection. Machina, Rappoport, Tversky, Khaneman, …) A similar problem exists in the financial world for managing a portfolio of investments. Other Nobel prizes have been awarded for systematic approaches to incorporating the risks involved.

But let’s get back to our expected value street light. For exponential decay the law of total probability yields $$V_π(s) = \sum_a π(a|s) \sum_{s',r'} p(s',r'|s,a)[r' + γ V_π(s')].$$ We want to find the optimal state-value function $V^*(s) = \max_π V_π(s)$. $$V^*(s) = \max_{a\in A} \sum_{s',r'} p(s',r'|s,a)[r' + γ V^*(s')].$$ is the Bellman optimality equation.

Exercise. Show $V^*(s) \ge V_π(s)$ for any policy $π$.

The action-value function for $π$ is $Q_π(s,a) = E[G_t\mid S_t = s, A_t = a]$. It is the state-value function for a given action. We want to find $Q^*(s,a) = \max_π Q_π(s,a)$. Note for exponential decay $$Q^*(s,a) = E[R_{t+1} + γ V^*(S_{t+1})|S_t = s, A_t = a].$$ gives the optimal action-value function.

Bandits

An $n$-armed bandit is a MDP with one state and $n$ actions. Solutions should explore the $n$ available actions and exploit the most promising. In this case the action-value function does not depend on the state. If we knew the reward distributions for each action then the optimal strategy would be to always select the action with the largest expected value but we don’t need to estimate each individual reward distribution in order to find the optimal policy.

The $ε$-greedy strategy selects the action maximizing the current action-value function with probability $1-ε$ and a random action with probability $ε$. The action-value function is updated based on the observed reward. Hopefully this will converge to $V^*$ and we can find a method to make this happen quickly.

Monte Carlo Methods

The first visit Monte Carlo prediction approximates the state-value function for a given policy. Choose an initial state-value function $V(s)$ and generate actions using $π$. For each state in the run update $V(s)$ to be the sample average of the returns.