Inverse Contextual Bandits without Rewards: Learning from a Non-Stationary Learner via Suffix Imitation
| Authors | Yuqi Kong et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2603.03778 |
| Download | |
| Categories | cs.LG, stat.ML |
Abstract
We study the Inverse Contextual Bandit (ICB) problem, in which a learner seeks to optimize a policy while an observer, who cannot access the learner's rewards and only observes actions, aims to recover the underlying problem parameters. During the learning process, the learner's behavior naturally transitions from exploration to exploitation, resulting in non-stationary action data that poses significant challenges for the observer. To address this issue, we propose a simple and effective framework called Two-Phase Suffix Imitation. The framework discards data from an initial burn-in phase and performs empirical risk minimization using only data from a subsequent imitation phase. We derive a predictive decision loss bound that explicitly characterizes the bias-variance trade-off induced by the choice of burn-in length. Despite the severe information deficit, we show that a reward-free observer can achieve a convergence rate of \tilde O(1/\sqrt{N}), matching the asymptotic efficiency of a fully reward-aware learner. This result demonstrates that a passive observer can effectively uncover the optimal policy from actions alone, attaining performance comparable to that of the learner itself.
Engineering Breakdown
Plain English
This paper tackles the Inverse Contextual Bandit (ICB) problem, where a learner optimizes a policy through exploration and exploitation, while an external observer tries to recover the underlying problem parameters by only watching the learner's actions—without access to rewards. The core challenge is that the learner's behavior shifts non-stationarily from exploration to exploitation over time, making it hard for the observer to learn from the action sequence. The authors propose Two-Phase Suffix Imitation, a framework that throws away early 'burn-in' data and uses empirical risk minimization on later-phase data to recover problem parameters. They derive theoretical bounds that characterize the bias-variance trade-off created by this approach, providing formal guarantees on parameter recovery accuracy.
Core Technical Contribution
The key innovation is the Two-Phase Suffix Imitation framework, which explicitly handles the non-stationarity problem in inverse contextual bandits by temporal segmentation. Rather than trying to learn from all observed actions, the framework strategically discards initial exploration-heavy data and focuses only on later imitation-phase data where the policy has stabilized toward exploitation. This simple idea—combined with empirical risk minimization—sidesteps the complex problem of modeling non-stationary action distributions. The authors provide a predictive decision loss bound that formally characterizes how the burn-in phase length trades off bias (from incomplete data) against variance (from a shorter training window), enabling principled parameter recovery from biased action sequences.
How It Works
The framework operates in two distinct phases. In Phase 1 (burn-in), the learner explores the environment to gather initial information about rewards and optimal actions; the observer sees these exploratory actions but discards them. In Phase 2 (imitation), the learner transitions to exploitation, settling into a more stable policy; the observer collects action sequences from this phase. The observer then formulates parameter recovery as an empirical risk minimization problem: given observed actions from Phase 2, find problem parameters (reward function, transition dynamics, etc.) that best explain those actions under the assumption of optimal or near-optimal behavior. The theoretical contribution derives a loss bound showing that the Phase 2 dataset contains both bias (because the learner may not have converged to the true optimal policy) and variance (because Phase 2 data is limited). The bound quantifies how choosing the burn-in cutoff point controls this trade-off, enabling the observer to select the optimal phase transition timing.
Production Impact
In real systems where you observe user behavior but cannot directly measure engagement or reward signals, this approach enables recovery of underlying user preferences and environment dynamics. For example, in recommendation systems, you observe which items users click/engage with as a proxy for the system's learned policy, but you cannot directly observe the reward signal the recommender optimized for—this framework lets you reverse-engineer the effective reward function. The practical benefit is avoiding the need to instrument intrusive reward logging; instead, you leverage the natural behavior transition as a signal. The trade-off is computational: you must choose the burn-in cutoff correctly (requires hyperparameter tuning or held-out validation), and you throw away useful early-phase data, potentially requiring longer total observation periods. Integration is straightforward—it layers on top of standard behavioral cloning pipelines, requiring only temporal segmentation of logged action data.
Limitations and When Not to Use This
The framework assumes that Phase 2 behavior is close to optimal, which may not hold if the learner's exploration-exploitation trade-off is poor or if the environment is non-stationary beyond the learner's control. The approach also requires knowing or estimating where the burn-in phase ends, and the loss bound is likely loose in practice, meaning the theoretical cutoff point may differ from the empirical optimum. The paper doesn't address what happens when the observer has no ground truth to validate the recovered parameters, making it unclear how to detect failure modes in production. Additionally, the framework is limited to settings where actions are informative about underlying parameters; in highly stochastic or high-dimensional action spaces, the action sequence alone may not carry enough signal for accurate parameter recovery.
Research Context
This work extends the contextual bandit literature by inverting the typical learning problem—instead of optimizing a policy given known rewards, the observer must infer rewards/parameters from policy behavior. It builds on foundational work in inverse reinforcement learning and behavioral cloning but applies it to the non-stationary setting of bandit learning, where most prior inverse RL assumes stationary expert policies. The two-phase approach is inspired by classical burn-in techniques in time-series analysis and adapts them to the bandit setting. This direction opens research into learning from latent-reward environments and could extend to more complex sequential decision-making (e.g., MDPs), where non-stationarity during learning is even more pronounced.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::