Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Log-Sum-Exponential Estimator for Off-Policy Evaluation and Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a log-sum-exponential (LSE) estimator for off-policy evaluation and learning from logged bandit feedback, with regret/bias/variance bounds under a bounded (1+ε)-th moment assumption and experiments on synthetic OPE and EMNIST/FMNIST-based OPL.
Problem
Off-policy evaluation and learning from logged bandit feedback suffer from high variance of IPS estimators, poor performance with estimated propensity scores, and heavy-tailed or noisy rewards.
Approach
Replace the linear IPS average with a non-linear log-sum-exponential aggregation of importance-weighted rewards with negative parameter lambda; negative lambda down-weights large outlying samples, recovers IPS as lambda approaches 0, and yields bounds under only a bounded (1+epsilon)-th moment of weighted reward.
Key results
- On synthetic OPE with alpha=1.4, LSE achieves MSE 0.670 versus 1.842 for IX, 4.232 for ES and 165.041 for PM.
- On EMNIST OPL with tau=10 and true propensities, LSE reaches 88.59% accuracy versus 88.61% for PM (best) and 79.43% for logging policy; under propensity noise b=0.01 LSE gets 82.15% vs 80.85% for PM.
- Regret upper bound converges at O(n^{-epsilon/(1+epsilon)}) under bounded (1+epsilon)-th moment, with epsilon=1 giving O(n^{-1/2}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=1, true propensity, no reward noise) | accuracy: 88.49 ± 0.04 vs 89.19 ± 0.03 | Hurt |
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=1, b=5, no reward noise) | accuracy: 88.94 ± 0.05 -> 89.16 ± 0.03 | Helped |
| Use LSE instead of ES | Off-policy learning · EMNIST (τ=1, b=0.0, no reward noise) | accuracy: 85.71 ± 0.04 -> 86.07 ± 0.01 | Helped |
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=1, true propensity, Pf=0.1) | accuracy: 89.08 ± 0.05 -> 89.29 ± 0.04 | Helped |
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=1, true propensity, Pf=0.5) | accuracy: 88.78 ± 0.03 vs 88.72 ± 0.08 | Hurt |
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=10, true propensity, no reward noise) | accuracy: 88.61 ± 0.04 vs 88.59 ± 0.03 | No clear effect |
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=10, b=5, no reward noise) | accuracy: 88.43 ± 0.07 vs 88.42 ± 0.07 | No clear effect |
| Use LSE instead of ES | Off-policy learning · EMNIST (τ=10, b=0.01, no reward noise) | accuracy: 81.07 ± 0.07 -> 82.15 ± 0.21 | Helped |
| Use LSE instead of PM | Off-policy learning · EMNIST (τ=10, true propensity, Pf=0.1) | accuracy: 88.22 ± 0.02 -> 88.29 ± 0.06 | Helped |
| Use LSE instead of OS | Off-policy learning · EMNIST (τ=10, true propensity, Pf=0.5) | accuracy: 89.09 ± 0.05 vs 88.71 ± 0.16 | Hurt |
| Use LSE instead of LS | Off-policy evaluation · Synthetic OPE (α=1.1) | MSE: 0.013 -> 0.009 | Helped |
| Use LSE instead of LS | Off-policy evaluation · Synthetic OPE (α=1.4) | MSE: 0.776 -> 0.670 | Helped |
Surprising findings
- In the EMNIST OPL table, PM and other baselines match or beat LSE in several settings (e.g., tau=1 with true propensities PM 89.19 vs LSE 88.49), so LSE is not uniformly best.
- The LSE-based regret bound with lambda set to -n^{-1/(1+epsilon)} requires n large relative to a sample-size threshold, and the bias bound only becomes small asymptotically.
Limitations
- Theory assumes finite policy set; extension to infinite policy classes relies on future analysis (VC/PAC-Bayes).
- Regret and bias bounds hold for negative lambda only; positive lambda is not covered by the analysis.
- Empirical gains are mixed: several baselines (PM, ES, OS) are equal or better in some EMNIST settings.
Experimental setup
Datasets: EMNIST FMNIST KuaiRec UCI datasets synthetic Gaussian/exponential-reward bandit data
Benchmarks: EMNIST FMNIST KuaiRec UCI datasets synthetic OPE bandit
Metrics: bias variance MSE deterministic accuracy
Baselines: IPS-TR PM ES IX SNIPS LS-LIN LS OS BanditNet
Builds on: inverse propensity score power-mean estimator exponential smoothing estimator implicit exploration estimator tilted empirical risk
Closest papers by meaning
- Variational Approach to Optimal IPS Estimator for Multi-logger Off-Policy Evaluation (NeurIPS 2026 · similarity 0.92)
- Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning (NeurIPS 2024 · similarity 0.90)
- Off-Policy Evaluation and Learning from Logged Bandit Feedback: Error Reduction via Surrogate Policy (ICLR 2019 · similarity 0.90)
- Optimal and Adaptive Off-policy Evaluation in Contextual Bandits (ICML 2017 · similarity 0.90)
- Off-policy estimation with adaptively collected data: the power of online learning (NeurIPS 2024 · similarity 0.88)
- Cross-Domain Off-Policy Evaluation and Learning for Contextual Bandits (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.