An agent with an inaccurate model of its environment faces a difficult choice: it can ignore the errors in its model and act in the real world in whatever way it determines is optimal with respect to its model. Alternatively, it can take a more conservative stance and eschew its model in favor of optimizing its behavior solely via real-world interaction. This latter approach can be exceedingly slow to learn from experience, while the former can lead to "planner overfitting" - aspects of the agent's behavior are optimized to exploit errors in its model. This paper explores an intermediate position in which the planner seeks to avoid overfitting through a kind of regularization of the plans it considers. We present three different approaches that demonstrably mitigate planner overfitting in reinforcement-learning environments.
Kolter2009a applied regularization techniques to LSTD @cite_9 with an algorithm they called LARS-TD. In particular, they argued that, without regularization, LSTD's performance depends heavily on the number of basis functions chosen and the size of the data set collected. If the data set is too small, the technique is prone to overfitting. They showed that @math and @math regularization yield a procedure that inherits the benefits of selecting good features while making it possible to compute the fixed point. Later work by liu2012regularized built on this work with the algorithm RO-TD, an @math regularized off policy Temporal Difference Learning method. Johns2010 cast the @math regularized fixed-point computation as a linear complementarity problem, which provides stronger solution-uniqueness guarantees than those provided for LARS-TD. petrik2010feature examined the approximate linear programming (ALP) framework for finding approximated value functions in large MDPs. They showed the benefits of adding an @math regularization constraint to the ALP that increases the error bound at training time and helps fight overfitting.
@cite_9
2072931156
We introduce two new temporal difference (TD) algorithms based on the theory of linear least-squares function approximation. We define an algorithm we call Least-Squares TD (LS TD) for which we prove probability-one convergence when it is used with a function approximator linear in the adjustable parameters. We then define a recursive version of this algorithm, Recursive Least-Square TD (RLS TD). Although these new TD algorithms require more computation per time-step than do Sutton‘s TD(λ) algorithms, they are more efficient in a statistical sense because they extract more information from training experiences. We describe a simulation experiment showing the substantial improvement in learning rate achieved by RLS TD in an example Markov prediction problem. To quantify this improvement, we introduce the TD error variance of a Markov chain, σTD, and experimentally conclude that the convergence rate of a TD algorithm depends linearly on σTD. In addition to converging more rapidly, LS TD and RLS TD do not have control parameters, such as a learning rate parameter, thus eliminating the possibility of achieving poor performance by an unlucky choice of parameters.