Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Provably Efficient Interactive-Grounded Learning with Personalized Reward
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.
Provides the first provably efficient sublinear-regret algorithms for interactive-grounded learning with context-dependent (personalized) feedback, using a Lipschitz reward estimator built from uniform-exploration inverse kinematics, with explore-then-exploit and inverse-gap-weighting variants.
Problem
Interactive-grounded learning with personalized rewards, where feedback depends on context as well as the latent reward, lacks theoretical guarantees; prior work only had empirical methods and step-function estimators can deviate due to finite-sample effects.
Approach
Construct a Lipschitz reward underestimator G(h_a(x,y), θ/α−σ, σ) from an inverse-kinematics predictor trained on uniformly random action data; it lower-bounds the true reward for all policies and matches it for the optimal policy, enabling explore-then-exploit and inverse-gap-weighting algorithms with O(T^{2/3}) regret.
Key results
- On MNIST, on-policy IGL with the Lipschitz estimator reaches 90.3% test accuracy (vs 89.4% with binary estimator); off-policy Lipschitz reaches 75.9% vs 72.6% binary.
- Theory: off-policy explore-then-exploit achieves O(T^{2/3}K^{2/3}sigma^{-2/3} log^{1/3}(|H|T)) regret; on-policy IGW achieves O(sqrt(KT Reg_Sq) + sigma^{-2/3}(KT)^{2/3} log^{1/3}(|H|T)).
- On the conversational dataset, the constructed reward is shown to lie below the true reward while the learner improves via text feedback alone (no quantitative accuracy reported in text).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Lipschitz reward estimator instead of the binary estimator (ablation) | Off-policy IGL · MNIST | Average Progressive Reward: 0.614 (0.012) -> 0.638 (0.042) | Helped |
| Use the Lipschitz reward estimator instead of the binary estimator (ablation) | Off-policy IGL · MNIST | Test Accuracy: 72.6% (1.5%) -> 75.9% (4.9%) | Helped |
| Use the Lipschitz reward estimator instead of the binary estimator (ablation) | On-policy IGL · MNIST | Average Progressive Reward: 0.718 (0.006) -> 0.740 (0.022) | Helped |
| Use the Lipschitz reward estimator instead of the binary estimator (ablation) | On-policy IGL · MNIST | Test Accuracy: 89.4% (4.0%) -> 90.3% (3.7%) | Helped |
Limitations
- Regret bounds depend on sigma^{-1}, which can be large for sparse rewards (e.g. O(s^2) for s-multi-label).
- Requires realizability and a lower-bound realizability assumption for the on-policy algorithm.
- Experiments are limited to MNIST and a single synthetic conversational dataset; off-policy results have high variance.
Experimental setup
Datasets: MNIST Chatbot Arena questions
Benchmarks: MNIST
Metrics: average progressive reward test accuracy
Baselines: Binary reward estimator (step-function thresholding) Off-policy IGL with binary reward
Builds on: Interaction-Grounded Learning (Xie et al., 2021) Maghakian et al. 2022 personalized IGL Inverse-gap weighting (Foster & Rakhlin 2020) Vovk aggregation
Closest papers by meaning
- An Information Theoretic Approach to Interaction-Grounded Learning (ICML 2024 · similarity 0.87)
- Capturing Individual Human Preferences with Reward Features (NeurIPS 2025 · similarity 0.84)
- Scaling Reward Modeling without Human Supervision (NeurIPS 2026 · similarity 0.84)
- Reward Learning from Multiple Feedback Types (ICLR 2025 · similarity 0.84)
- Learning from negative feedback, or positive feedback or both (ICLR 2025 · similarity 0.84)
- Provably Efficient Online RLHF with One-Pass Reward Modeling (NeurIPS 2025 · similarity 0.84)
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.