Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The authors investigate two-arm contextual bandits with arm-specific single indices and a shared unknown monotone link, introducing Natural Boundary Learning (NBL) to estimate the decision boundary directly rather than estimating latent reward functions. By leveraging sequential Stein contrasts, NBL exploits the fact that monotone links reduce policy optimization purely to directional contrasts between arms. The authors prove that when a decision stability coefficient derived from Riemannian dynamics and convex elicitation geometry holds, NBL contracts to the optimal boundary and achieves $O(\log n)$ expected regret under link misspecification.
Contextual bandits don't actually need reward estimation—exploiting the elicitation geometry of shared monotone links lets algorithms target the decision boundary directly to secure logarithmic regret under severe functional misspecification.
We study two-arm contextual bandits with arm-specific single indices and a shared unknown monotone link. Monotonicity makes the optimal action depend only on the contrast between the index directions, hence arm-specific reward functions need not be estimated. We introduce Natural Boundary Learning (NBL), a greedy procedure that uses a sequential Stein contrast to learn the optimal boundary directly, without estimating the reward functions or the common link. We characterize the local Riemannian dynamics of NBL through a decision stability coefficient balancing arm separation, link geometry, and the context distribution. We show that this stability is connected to the elicitation geometry of the underlying convex potential. Under local decision stability, NBL contracts toward the optimal boundary and achieves $O(\log n)$ expected regret. Numerical experiments illustrate the predicted stability regimes and compare NBL with a parametric greedy benchmark under link misspecification.