SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits

• URL: http://arxiv.org/abs/2301.12357v3
• Date: Fri, 1 Mar 2024 01:24:03 GMT
• Title: SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits
• Authors: Subhojyoti Mukherjee, Qiaomin Xie, Josiah Hanna, Robert Nowak
• Abstract summary: We study the problem of optimal data collection for policy evaluation in linear bandits. We first formulate an optimal design for weighted least squares estimates in the heteroscedastic linear bandit setting. We then use this formulation to derive the optimal allocation of samples per action during data collection.
• Score: 13.02672341061555
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• OPERA: Automatic Offline Policy Evaluation with Re-weighted Aggregates of Multiple Estimators [13.408838970377035]
  offline policy evaluation (OPE) allows us to evaluate and estimate a new sequential decision-making policy's performance. We propose a new algorithm that adaptively blends a set of OPE estimators given a dataset without relying on an explicit selection using a statistical procedure. Our work contributes to improving ease of use for a general-purpose, estimator-agnostic, off-policy evaluation framework for offline RL.
  arXiv  Detail & Related papers  (2024-05-27T23:51:20Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Policy Gradient with Active Importance Sampling [55.112959067035916]
  Policy gradient (PG) methods significantly benefit from IS, enabling the effective reuse of previously collected samples. However, IS is employed in RL as a passive tool for re-weighting historical samples. We look for the best behavioral policy from which to collect samples to reduce the policy gradient variance.
  arXiv  Detail & Related papers  (2024-05-09T09:08:09Z)
• Off-Policy Evaluation for Large Action Spaces via Policy Convolution [60.6953713877886]
  Policy Convolution family of estimators uses latent structure within actions to strategically convolve the logging and target policies. Experiments on synthetic and benchmark datasets demonstrate remarkable mean squared error (MSE) improvements when using PC.
  arXiv  Detail & Related papers  (2023-10-24T01:00:01Z)
• Importance-Weighted Offline Learning Done Right [16.4989952150404]
  We study the problem of offline policy optimization in contextual bandit problems. The goal is to learn a near-optimal policy based on a dataset of decision data collected by a suboptimal behavior policy. We show that a simple alternative approach based on the "implicit exploration" estimator of citet2015 yields performance guarantees that are superior in nearly all possible terms to all previous results.
  arXiv  Detail & Related papers  (2023-09-27T16:42:10Z)
• Provable Offline Preference-Based Reinforcement Learning [95.00042541409901]
  We investigate the problem of offline Preference-based Reinforcement Learning (PbRL) with human feedback. We consider the general reward setting where the reward can be defined over the whole trajectory. We introduce a new single-policy concentrability coefficient, which can be upper bounded by the per-trajectory concentrability.
  arXiv  Detail & Related papers  (2023-05-24T07:11:26Z)
• Improved Policy Evaluation for Randomized Trials of Algorithmic Resource Allocation [54.72195809248172]
  We present a new estimator leveraging our proposed novel concept, that involves retrospective reshuffling of participants across experimental arms at the end of an RCT. We prove theoretically that such an estimator is more accurate than common estimators based on sample means.
  arXiv  Detail & Related papers  (2023-02-06T05:17:22Z)
• ReVar: Strengthening Policy Evaluation via Reduced Variance Sampling [10.925914554822343]
  We develop theory for optimal data collection within the class of tree-structured MDPs. We empirically validate that ReVar leads to policy evaluation with mean squared error comparable to the oracle strategy.
  arXiv  Detail & Related papers  (2022-03-09T03:41:15Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  We make the first attempt to study risk-sensitive deep reinforcement learning under the average reward setting with the variance risk criteria. We propose an actor-critic algorithm that iteratively and efficiently updates the policy, the Lagrange multiplier, and the Fenchel dual variable.
  arXiv  Detail & Related papers  (2020-12-28T05:02:26Z)
• Policy Optimization as Online Learning with Mediator Feedback [46.845765216238135]
  Policy Optimization (PO) is a widely used approach to address continuous control tasks. In this paper, we introduce the notion of mediator feedback that frames PO as an online learning problem over the policy space. We propose an algorithm, RANDomized-exploration policy Optimization via Multiple Importance Sampling with Truncation (RIST) for regret minimization.
  arXiv  Detail & Related papers  (2020-12-15T11:34:29Z)
• Distributionally Robust Batch Contextual Bandits [20.667213458836734]
  Policy learning using historical observational data is an important problem that has found widespread applications. Existing literature rests on the crucial assumption that the future environment where the learned policy will be deployed is the same as the past environment. In this paper, we lift this assumption and aim to learn a distributionally robust policy with incomplete observational data.
  arXiv  Detail & Related papers  (2020-06-10T03:11:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.