Reinforcement learning (example: maze solving)

Simple "reinforcement learning" models can solve surprisingly complex problems, and can be used to model human and animal behavior. The idea is to track the values of states and actions within those states, and gradually learn through trial and error which are the most valuable actions within each state. The values of good and bad outcomes can trickle back to earlier states through something called "temporal difference learning." The key to this is immediately updating the estimated values of actions with immediate results and with estimates of their down-stream consequences. In this demo, we'll see how a simple RL learner can figure out the shortest path to a goal state, where it gets a lot of reward, in just a few iterations of temporal difference learning.

We will use a method called Q-learning. In one form of Q learning, states are represented by the variable \(s\). Each state is associated with a set of actions, with individual actions represented by the variable \(a\). The learner maintains a value, represented by \(Q\), of each possible state-action pair -- \(Q(s,a)\). When an action is taken, a new state is achieved, and then the \(Q(s,a)\) corresponding to the action taken is updated. Two things feed these updates: (1) A rewarding or punishing event might occur. (2) The estimated future value of the next state, \(s'\), is fed back to the \(Q(s,a)\). How do we determine that future value? Well, in this case we simply take the maximum of possible \(Q\) for the next state, that is, the \(Q\) for the action \(a'\) with the highest Q-value for state \(s'\). That's because this estimates the future value of that new state.

Thinking through the implementation of this update, we have to consider a few things. First, we might not want to just replace our current estimate with immediate reward + future value of the next state -- the environment could be more complicated or noisy than such an update would be optimal for. So, we will update \(Q(s,a)\) by calculating the difference between what we expected to happen (exactly our old \(Q(s,a)\)) and what actually happened -- the "reward prediction error," or usually referred to as the "temporal difference" in this context, weighted by a factor called the learning rate (referred to here with the symbol \(\alpha\)). Additionally, we might prefer not to take the next state's maximum future reward estimate for granted -- for example, future rewards might be noisier or worth less compared to immediate rewards. We will discount that element with a further factor called the discount factor and referred to with the symbol \(\lambda\). OK, here's the full equation for updating after taking action \(a\) from state \(s\), resulting in our being in state \(s'\): \[Q_{t+1}(s,a)=\underbrace{Q_{t}(s,a)}_{\text{old value}}+\underbrace{\alpha}_{\text{learning rate}}\times\overbrace{[\underbrace{r_t}_{\text{reward}}+\underbrace{\gamma}_{\text{discount factor}} \times \underbrace{max_{a'}Q(s',a')}_{\text{estimated future value of next state}}-Q_{t}(s,a)]}^{\text{temporal difference error or reward prediction error}}\]

So, on each step, how do we make a choice? There are many ways to go from the Q-table of a present state to a choice. First, we could just choose the maximum current Q-value, i.e. the value of \(a\) that satisfies \(max_{a}Q(s,a)\). A problem with that is that we might get stuck in a pattern than isn't optimal, simple because our first few choices in this state turned out a certain way. So, in order to be sure that we'll converge on good solutions (and stay adaptive in a changing environment), we should also make some random choices sometimes. A simple way would be to explore with some probability, we'll call it \(\epsilon\), and otherwise pick the action with the best current Q-value. This basic tension, between maximizing rewards based on what we know and exploring the environment to discover what we're missing, is called the explore-exploit tradeoff. The strategy described above is called the epsilon-greedy strategy. There are lots of other solutions of greater complexity. For instance, one solution referred to as softmax turns all Q-values into probabilities of making each choice, with higher Q-values associated with larger probabilities, and includes a parameter that controls the degree of randomness (the extent to which these action probabilities tend to be even despite differing Q-values).