SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits
In this paper, we study the problem of optimal data collection for policy evaluation in linear bandits. In policy evaluation, we are given a target policy and asked to estimate the expected reward it will obtain when executed in a multi-armed bandit environment. Our work is the first work that focuses on such optimal data collection strategy for policy evaluation involving heteroscedastic reward noise in the linear bandit setting. We first formulate an optimal design for weighted least squares estimates in the heteroscedastic linear bandit setting that reduces the MSE of the value of the target policy. We then use this formulation to derive the optimal allocation of samples per action during data collection. We then introduce a novel algorithm SPEED (Structured Policy Evaluation Experimental Design) that tracks the optimal design and derive its regret with respect to the optimal design. Finally, we empirically validate that SPEED leads to policy evaluation with mean squared error comparable to the oracle strategy and significantly lower than simply running the target policy.
Code (0)
등록된 구현이 없습니다.
Tasks
Experimental DesignMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
SVRG for Policy Evaluation with Fewer Gradient Evaluations
Stochastic variance-reduced gradient (SVRG) is an optimization method originally designed for tackling machine learning problems with a finite sum structure. SVRG was later shown to work for policy evaluation, a problem …
Reinforcement LearningReinforcement Learning (RL)One-Shot Averaging for Distributed TD($λ$) Under Markov Sampling
We consider a distributed setup for reinforcement learning, where each agent has a copy of the same Markov Decision Process but transitions are sampled from the corresponding Markov chain independently by each agent. We …
Linear Complementarity for Regularized Policy Evaluation and Improvement
Recent work in reinforcement learning has emphasized the power of L1 regularization to perform feature selection and prevent overfitting. We propose formulating the L1 regularized linear fixed point problem as a linear c…
feature selectionReinforcement LearningReinforcement Learning (RL)Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks
This paper proposes a \emph{fully asynchronous} scheme for the policy evaluation problem of distributed reinforcement learning (DisRL) over directed peer-to-peer networks. Without waiting for any other node of the networ…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Quantum Reinforcement Learning via Policy Iteration
Quantum computing has shown the potential to substantially speed up machine learning applications, in particular for supervised and unsupervised learning. Reinforcement learning, on the other hand, has become essential f…
Decision Makingreinforcement-learningReinforcement LearningReinforcement Learning (RL)