Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice
The study investigates Mirror Descent Value Iteration (MDVI) for linear Markov Decision Processes using function approximation. It proves that standard least-squares regression is insufficient for minimax optimality; achieving it requires weighting the regression by the variance of an estimated optimal value function of the next state. This leads to new algorithms like VWLS-MDVI and DVW.