Abstract
At the dawn of the computer age in the 1960s, Bellman and his co-workers already found it useful to use linear function approximation to solve some multistage (or sequential) planning problems. Their approach was simple: Just use function approximation to avoid state-space discretization and thus keep all computation poly-time, while also controlling for accuracy. However, the question of when and how is this possible has eluded researchers for at least 50 years. The partial results obtained suggested that the approximation spaces used need to have an intricate relationship to the problem to be solved and it may not be sufficient that the target function (say, the optimal value function) lies in this space. In this talk I will give an overview of recent work in this area, which essentially closed most of the open questions in the simplest finite horizon setting. While the picture that emerges is interesting, most of the results are negative. The conclusion is that the approximation spaces indeed be better special, or generality needs to be sacrificed in some other way.