Off-Policy Evaluation for Large Action Spaces via Embeddings

Published in

International Conference on Machine Learning(2022)

External Links:

Generate Graph

TL;DR

This work proposes a new OPE estimator that leverages marginalized importance weights when action embeddings provide structure in the action space, and analyzes the conditions under which the action embedding provides statistical benefits over conventional estimators.

Abstract

Off-policy evaluation (OPE) in contextual bandits has seen rapid adoption in real-world systems, since it enables offline evaluation of new policies using only historic log data. Unfortunately, when the number of actions is large, existing OPE estimators -- most of which are based on inverse propensity score weighting -- degrade severely and can suffer from extreme bias and variance. This foils the use of OPE in many applications from recommender systems to language models. To overcome this issue, we propose a new OPE estimator that leverages marginalized importance weights when action embeddings provide structure in the action space. We characterize the bias, variance, and mean squared error of the proposed estimator and analyze the conditions under which the action embedding provides statistical benefits over conventional estimators. In addition to the theoretical analysis, we find that the empirical performance improvement can be substantial, enabling reliable OPE even when existing estimators collapse due to a large number of actions.

Authors

Yuta Saito

4 papers

T. Joachims

1 papers

References70 items

Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model

Counterfactual Learning and Evaluation for Recommender Systems: Foundations, Implementations, and Recent Advances

Evaluating the Robustness of Off-Policy Evaluation

Semiparametric estimation of long-term treatment effects

Control Variates for Slate Off-Policy Evaluation

Off-Policy Evaluation for Large Action Spaces via Embeddings

Published in

International Conference on Machine Learning(2022)

External Links:

Generate Graph

TL;DR

Abstract

Authors

Yuta Saito

4 papers

T. Joachims

1 papers

References70 items

Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model

Counterfactual Learning and Evaluation for Recommender Systems: Foundations, Implementations, and Recent Advances

Evaluating the Robustness of Off-Policy Evaluation

Semiparametric estimation of long-term treatment effects

Control Variates for Slate Off-Policy Evaluation

Optimal Off-Policy Evaluation from Multiple Logging Policies

Learning from eXtreme Bandit Feedback

Doubly Robust Estimator for Ranking Metrics with Post-Click Conversions

Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation

Debiasing Grid-based Product Search in E-commerce

Counterfactual Evaluation of Slate Recommendations with Sequential Reward Interactions

Using Experiments to Correct for Selection in Observational Studies

Off-policy Bandits with Deficient Support

On the role of surrogates in the efficient estimation of treatment effects with limited outcome data

Adaptive Estimator Selection for Off-Policy Evaluation

Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning

Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling

Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes

Doubly robust off-policy evaluation with shrinkage

Balanced Off-Policy Evaluation in General Action Spaces

Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling

CAB: Continuous Adaptive Blending for Policy Evaluation and Learning

Semi-Parametric Efficient Policy Learning with Continuous Actions

Off-Policy Policy Gradient with Stationary Distribution Correction

Introduction to Multi-Armed Bandits

Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting

The Natural Language of Actions

Learning Action Representations for Reinforcement Learning

Efficient Counterfactual Learning from Bandit Feedback

Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation

Efficient Counterfactual Learning from Bandit Feedback

Offline Evaluation of Ranking Policies with Click Models

Policy Evaluation and Optimization with Continuous Treatments

More Robust Doubly Robust Off-policy Evaluation

Cross-fitting and fast remainder rates for semiparametric estimation

Optimal and Adaptive Off-policy Evaluation in Contextual Bandits

Off-policy evaluation for slate recommendation

A Neural Click Model for Web Search

Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning

Deep Reinforcement Learning in Large Discrete Action Spaces

The Self-Normalized Estimator for Counterfactual Learning

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

High Confidence Policy Improvement

Click Models for Web Search

Doubly Robust Policy Evaluation and Optimization

Bandits and Experts in Metric Spaces

Thompson Sampling for Contextual Bandits with Linear Payoffs

Fast Reinforcement Learning with Large Action Sets Using Error-Correcting Output Codes for MDP Factorization

Contextual Bandits with Linear Payoff Functions

Generalized Value Functions for Large Action Sets

Scikit-learn: Machine Learning in Python

Using continuous action spaces to solve discrete problems

Efficient multiple-click models in web search

Nearly Tight Bounds for the Continuum-Armed Bandit Problem

Optimal pointwise adaptive methods in nonparametric estimation

The Continuum-Armed Bandit Problem

A Generalization of Sampling Without Replacement from a Finite Universe

Improved Estimator Selection for Off-Policy Evaluation

Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning

pseudoinverse (PI) estimator was shown to provide an exponential gain in the sample complexity over IPS

2021) define a more general weight, ((1− λ)w(x, a) + λ) 1s , with an additional hyperparameter s. The above instance is a special case with s = 1, which is the main proposal

Data-Driven Action Feature Selection Based on

Some recent works also tackle how to learn useful action representations from only available data

2020a) or under model misspecification (Farajtabar et al., 2018). Though there are a number of extensions of DR both in bandits (as described above) and RL

Batch learning from logged bandit feedback through counterfactual risk minimization

The MIPS estimator along with the exact and greedy versions of embedding dimension selection is now implemented in the OBP package.7

rely on what is called zooming algorithms, which gradually zoom in to the more promising regions of the action space to achieve data-dependent regret bounds. Further works are surveyed

are made to capture different types of user behaviors to control the bias-variance trade-off in OPE

Field of Study

Computer ScienceMathematics

Journal Information

Name

ArXiv

Volume

abs/2005.00687

Venue Information

Name

International Conference on Machine Learning

Type

conference

URL

https://icml.cc/

Alternate Names

ICML
Int Conf Mach Learn