Multi-task reinforcement learning with linear approximator under group sparsity assumption

This thesis introduces an original Multi-Task Sparse Fitted Q Iteration algorithm, and includes a theoretical analysis on its performance guarantees, as well as the introduction of a new optimization method to efficiently compute it and experiments to validate it. The powerful modeling tools of Markov Decision Processes and function approximation allows Reinforcement Learning algorithms to efficiently solve complex control problems defined on continuous domains. One main drawback of function approximation, and therefore also of Approximate Reinforcement Learning techniques, is the large number of samples needed for the learning process as the dimensionality of the problem increases. Using a restricted class of approximators, such as the linear models used in this thesis, can provide good results with a number of samples linear in the number of features. A restricted model introduces bias, so a common approach is to use a large number of features to describe the problem, in the hope that the space spanned by this features will contain a good representation. To avoid overfitting the large number of parameters introduced, many regularization techniques can be used. In particular, when the representation is sparse in its parameters, the approximator can exploit a number of parameters exponential in the number of samples, as long as most of the parameters will be equal to zero. In this thesis we will further increase this bound by solving together a set of tasks that share a common sparse representation. This property, called group sparsity, will allow us to keep increasing the number of features past the exponential limit as long as suitable new tasks are added linearly. This group sparse approach will allow us to efficiently express the problem as a sequence of optimization problems with matrix norm regularization. In addition we will also explore the possibility of learning a new group sparse matrix representation when the original problem is apparently not group sparse. This could expand the algorithm potential applications.