Reinforcement Learning and Stochastic Optimization

Part V – Lookahead Policies

Lookahead policies are based on estimates of the impact of a decision on the future. There are two broad strategies for doing this:

• Value function approximations If we are in a state S_t and take an action x_t, then we observe new information W_t+1 (which is random at time t) which takes us to a new state S_t+1, we might be able to approximate the value of being in state S_t+1. We can then use this to help us make a better decision x_t now if we can do a good job of approximating the value of being in state.
• Direct lookahead approximations Here we explicitly plan decisions now, x_t, and into the future, x_t+1,...,x_t+H, to help us make the best decision x_t to implement now. The problem in stochastic models is that the decisions x_tt for t^' > t depend on future information, so they are random.

The choice between using value functions versus direct lookaheads boils down to a single equation which gives the optimal policy at time t when we are in state S:

  (13.37)

The challenge is balancing the contributions now, given by C(S_t,x_t), against future contributions. If we could compute the future contributions, this would be an optimal policy. However, computing future contributions in the presence of a (random) sequential information process is almost always computationally intractable.

There are problems where we can create reasonable approximations of the future contributions. ...