# Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 35 references that are in the map.
- First posted on arXiv 9 Feb 2026.

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

- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (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)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Learning End-to-End Goal-Oriented Dialog](https://mlsanity.com/paper/1605.07683/) (2016)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Building a Conversational Agent Overnight with Dialogue Self-Play](https://mlsanity.com/paper/1801.04871/) (2018)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Interpretable User Satisfaction Estimation for Conversational Systems with Large Language Models](https://mlsanity.com/paper/2403.12388/) (2024)
- [Accelerated Robot Learning via Human Brain Signals](https://mlsanity.com/paper/1910.00682/) (2019)
- [Formalizing Learning from Language Feedback with Provable Guarantees](https://mlsanity.com/paper/2506.10341/) (2025)
- [Revisiting Popularity and Demographic Biases in Recommender Evaluation and Effectiveness](https://mlsanity.com/paper/2110.08353/) (2021)
- [Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP](https://mlsanity.com/paper/2207.11126/) (2022)
- [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)
- [Learning Efficiently Function Approximation for Contextual MDP](https://mlsanity.com/paper/2203.00995/) (2022)
- [Interaction-Grounded Learning](https://mlsanity.com/paper/2106.04887/) (2021)
- [Eluder-based Regret for Stochastic Contextual MDPs](https://mlsanity.com/paper/2211.14932/) (2022)
- [Personalized Reward Learning with Interaction-Grounded Learning (IGL)](https://mlsanity.com/paper/2211.15823/) (2022)
- [Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation](https://mlsanity.com/paper/2303.01464/) (2023)
- [Review-based Recommender Systems: A Survey of Approaches, Challenges and Future Perspectives](https://mlsanity.com/paper/2405.05562/) (2024)
- [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)
- [Using LLMs to Investigate Correlations of Conversational Follow-up Queries with User Satisfaction](https://mlsanity.com/paper/2407.13166/) (2024)
- [Provably Efficient Interactive-Grounded Learning with Personalized Reward](https://mlsanity.com/paper/2405.20677/) (2024)
- [An Information Theoretic Approach to Interaction-Grounded Learning](https://mlsanity.com/paper/2401.05015/) (2024)

## Abstract (arXiv)

In this paper, we study Interaction-Grounded Learning (IGL) [Xie et al., 2021], a paradigm designed for realistic scenarios where the learner receives indirect feedback generated by an unknown mechanism, rather than explicit numerical rewards. While prior work on IGL provides efficient algorithms with provable guarantees, those results are confined to single-step settings, restricting their applicability to modern sequential decision-making systems such as multi-turn Large Language Model (LLM) deployments. To bridge this gap, we propose a computationally efficient algorithm that achieves a sublinear regret guarantee for contextual episodic Markov Decision Processes (MDPs) with personalized feedback. Technically, we extend the reward-estimator construction of Zhang et al. [2024a] from the single-step to the multi-step setting, addressing the unique challenges of decoding latent rewards under MDPs. Building on this estimator, we design an Inverse-Gap-Weighting (IGW) algorithm for policy optimization. Finally, we demonstrate the effectiveness of our method in learning personalized objectives from multi-turn interactions through experiments on both a synthetic episodic MDP and a real-world user booking dataset.