# Provably Efficient Interactive-Grounded Learning with Personalized Reward

arXiv: https://arxiv.org/abs/2405.20677 · HTML: https://mlsanity.com/paper/2405.20677/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 31 May 2024.

## Builds on (most cited first, 19 of 19)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Practical Contextual Bandits with Feedback Graphs](https://mlsanity.com/paper/2302.08631/) (2023)
- [Contextual bandits with surrogate losses: Margin bounds and efficient algorithms](https://mlsanity.com/paper/1806.10745/) (2018)
- [Interaction-Grounded Learning](https://mlsanity.com/paper/2106.04887/) (2021)
- [Personalized Reward Learning with Interaction-Grounded Learning (IGL)](https://mlsanity.com/paper/2211.15823/) (2022)
- [Interaction-Grounded Learning with Action-inclusive Feedback](https://mlsanity.com/paper/2206.08364/) (2022)
- [Efficient Contextual Bandits with Uninformed Feedback Graphs](https://mlsanity.com/paper/2402.08127/) (2024)
- [An Information Theoretic Approach to Interaction-Grounded Learning](https://mlsanity.com/paper/2401.05015/) (2024)

## Built on by (most cited first, 3 of 3)

- [SynthesizeMe! Inducing Persona-Guided Prompts for Personalized Reward Models in LLMs](https://mlsanity.com/paper/2506.05598/) (2025)
- [P-GenRM: Personalized Generative Reward Model with Test-time User-based Scaling](https://mlsanity.com/paper/2602.12116/) (2026)
- [Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback](https://mlsanity.com/paper/2602.08307/) (2026)

## Abstract (arXiv)

Interactive-Grounded Learning (IGL) [Xie et al., 2021] is a powerful framework in which a learner aims at maximizing unobservable rewards through interacting with an environment and observing reward-dependent feedback on the taken actions. To deal with personalized rewards that are ubiquitous in applications such as recommendation systems, Maghakian et al. [2022] study a version of IGL with context-dependent feedback, but their algorithm does not come with theoretical guarantees. In this work, we consider the same problem and provide the first provably efficient algorithms with sublinear regret under realizability. Our analysis reveals that the step-function estimator of prior work can deviate uncontrollably due to finite-sample effects. Our solution is a novel Lipschitz reward estimator which underestimates the true reward and enjoys favorable generalization performances. Building on this estimator, we propose two algorithms, one based on explore-then-exploit and the other based on inverse-gap weighting. We apply IGL to learning from image feedback and learning from text feedback, which are reward-free settings that arise in practice. Experimental results showcase the importance of using our Lipschitz reward estimator and the overall effectiveness of our algorithms.