Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing
J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun · 2025
Read Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing by J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10826.txt.
Introduction
Jon Ryu and co-authors present a 2025 paper on learning from logged bandit data. In offline bandit problems, a past policy already gathered the data. The learner must pick or train a better policy from that fixed log. Bad picks waste the log, and naive training can chase noise. The team offers gains on both fronts: picking among policies and training a new one.
Their picking method uses a betting-style confidence bound on weighted rewards. Theory shows a sharper guarantee that adapts to variance in the data. For training, they propose a general condition that trades bias against variance in a new way. One case, called freezing, keeps variance low and suits small data sets. Ad and care systems both learn from logged choices. Sharper offline tools mean fewer risky live tests before a policy earns trust.
Catalog record
| CREATOR | J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10826
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun Abstract We consider off-policy selection and learning in contextual bandits, where the learner aims to select or train a reward-maximizing policy using data collected by a fixed behavior policy. Our contribution is two-fold. First, we propose a novel off-policy selection method that leverages a new betting-based confidence bound applied to an inverse propensity weight sequence. Our theoretical analysis reveals that this method achieves a significantly improved, variance-adaptive guarantee over prior work. Second, we propose a novel and generic condition on the optimization objective for off-policy learning that strikes a different balance between bias and variance. One special case, which we call freezing, tends to induce low variance, which is preferred in small-data regimes. Our analysis shows that it matches the best existing guarantees. In our empirical study, our selection method outperforms existing methods, and freezing exhibits improved performance in small-sample regimes. \coltauthor Massachusetts Institute of Technology and University of Wisconsin-Madison and Cornell University and University of Arizona and keywords offline contextual bandits; confidence bounds; martingale; second-order bounds 1 Introduction The offline contextual bandit problem has emerged as a critical area of study in sequential decision-making, with significant implications for decision systems for various domains including recommendation ( Li et al., 2010 ) and online advertising ( Schwartz et al., 2017 ) . In this problem, a behavior policy \pi_{\mathsf{ref}}(a|x) is deployed in the environment for a nontrivial period of time, where the policy defines a conditional distribution over the actions a (e.g., items to be recommended) given each context information x (e.g., user being served). Specifically, at each time step t\in[n]\triangleq\{1,\ldots,n\} , an agent observes a context x_{t}\sim\mathcal{D} from an unknown distribution \mathcal{D} , takes an action a_{t}\sim\pi_{\mathsf{ref}}(a|x_{t}) , and then receives a reward r_{t}=r(x_{t},a_{t})\in[0,1] where r is an unknown (possibly stochastic) reward function. Given offline logs of interactions D_{n}\triangleq\{(x_{t},a_{t},r_{t})\}_{t=1}^{n} obtained via the behavior policy, we wish to find a policy \pi that maximizes the expected reward \mu(\pi)\triangleq\EE_{x\sim\mathcal{D},a\sim\pi(a|x)}[r(x,a)] , which we call the value of the policy. This setting is called off-policy , in contrast to its online counterpart, where a policy can be updated continually using feedback from the environment. While online interactions may allow for more effective policy optimization, in many real-world scenarios this is either infeasible due to system constraints or too costly due to operational risks. The offline problem naturally arises as a viable alternative in this context. \underbrace{\sqrt{\EE\biggl[{\frac{(\tilde{r}_{1}^{\pi^{*}}-v(\pi^{*}))^{2}}{1+\beta(\tilde{r}_{1}^{\pi^{*}}\!-\!v(\pi^{*}))}}\biggr]}}_{\textstyle\text{PUB ({ours}; see Eq.~\eqref{eq:selection_refined})}}\leq\displaystyle\EE\biggl[{\frac{(\tilde{r}_{1}^{\pi^{*}}-v(\pi^{*}))^{2}}{1+\beta(\tilde{r}_{1}^{\pi^{*}}\!-\!v(\pi^{*}))}}\biggr]\lesssim\!\!\underbrace{1\!+\!\EE\biggl[{\frac{(\tilde{r}_{1}^{\pi^{*}})^{2}}{1+\beta\tilde{r}_{1}^{\pi^{*}}}}\biggr]}_{\textstyle\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{sakhi24logarithmic}{\@@citephrase{(}}{\@@citephrase{)}}}}}\leq\!\!\underbrace{1\!+\!\EE\biggl[\frac{(\tilde{r}_{1}^{\pi^{\star}})^{2}}{\pi^{\star}r+\beta\tilde{r}_{1}^{\pi^{\star}}}\biggr]}_{\textstyle\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{gabbianelli24importance}{\@@citephrase{(}}{\@@citephrase{)}}}}} . (a) Off-Policy Selection \underbrace{\EE\biggl[\frac{(\tilde{r}_{1}^{\pi^{\star}})^{2}}{c_{u}+\gamma\tilde{r}_{1}^{\pi^{\star}}}\biggr]}_{\textstyle\shortstack{\text{Solve \eqref{eq:op-learning-alg-0} + Assumption~\ref{ass:phi-new} ({ours}; see Eq.~\eqref{eq:learning})} \\ \text{\& \cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{sakhi24logarithmic}{\@@citephrase{(}}{\@@citephrase{)}}}}}}\leq\underbrace{\EE\biggl[\frac{(\tilde{r}_{1}^{\pi^{\star}})^{2}}{\pi^{\star}r+\gamma\tilde{r}_{1}^{\pi^{\star}}}\biggr]}_{\textstyle\text{\cite[citet]{\@@bibref{Authors Phrase1YearPhrase2}{gabbianelli24importance}{\@@citephrase{(}}{\@@citephrase{)}}}}}. (b) Off-Policy Learning Figure 1: Comparison of different bounds on the offline regret (see Eq. ( 1.2 )) for the off-policy (a) selection and (b) learning where \beta\approx\sqrt{1/n} in (a), and \gamma>0 in (b) is a hyperparameter. We hide a factor of \sqrt{1/n} and other constants. The symbol above \lesssim holds for n sufficiently large. For selection, our method achieves an improved bound. For learning, we propose a broad family of methods that achieves the same order of bound as Sakhi et al. (2024) . The main challenge in such an offline setting is in the discrepancy between the behavior policy used to log the offline data and the set of candidate policies whose performance we wish to evaluate. That is, we cannot simply use the offline data D_{n} to estimate the expected reward of an arbitrary policy \pi , since \pi may choose actions that are different from a_{t} ’s chosen by \pi_{\mathsf{ref}} , in which case we have not observed the corresponding rewards. This is in stark contrast to the supervised learning setup where a classifier’s generalization error can be estimated by simply computing the average error on a test dataset. To circumvent the problem, researchers have proposed unbiased estimators of the expected reward of a policy, such as the Importance Weighted (IW) estimator 1 1 1 Also known as Inverse Propensity Score (IPS) or Inverse Propensity Weighting (IPW) estimators. ( Horvitz and Thompson, 1952 ; Liu et al., 2020 ) and Doubly Robust (DR) estimator ( Robins and Rotnitzky, 1995 ) , with numerous extensions of them. The IW estimator is defined as \displaystyle\hat{\mu}_{n}^{\mathsf{IW}}(\pi)\triangleq\frac{1}{n}\sum_{t=1}^{n}\tilde{r}_{t}^{\pi},\text{~~ where ~~}\tilde{r}_{t}^{\pi}=w_{t}^{\pi}r_{t}, (1.1) is called the importance-weighted reward , and we refer to w_{t}^{\pi}\triangleq\frac{\pi(a_{t}|x_{t})}{\pi_{\mathsf{ref}}(a_{t}|x_{t})} as the importance weight. Depending on the goal, there are three representative types of off-policy (OP) problems. Below, we contrast each with its counterpart in a supervised learning setup. • Off-policy evaluation : Given a policy \pi , we wish to estimate its value (i.e., expected reward). In supervised learning, this corresponds to estimating the generalization error of a classifier using test data or obtaining confidence bounds for it. • Off-policy selection : Given \Pi , a finite set of candidate policies, we wish to find the best policy—that is, the one with the highest expected reward (i.e., value). In supervised learning, this corresponds to performing model selection using hold-out validation data. • Off-policy learning (optimization) : Given a policy class \Pi (typically with |\Pi|=\infty , as in the case of neural-network policies), we wish to find the best policy \pi that achieves the highest value. In supervised learning, this corresponds to learning a classifier using training data. In selection and learning, we wish to establish a guarantee on the offline regret (or suboptimality gap) for the policy \hat{\pi}\in\Pi selected by an algorithm, which is defined as, for \pi^{\star}\triangleq\arg\max_{\pi\in\Pi}\mu(\pi) , \displaystyle\mathsf{Reg}_{n}(\hat{\pi})\triangleq\mu(\pi^{\star})-\mu(\hat{\pi}). (1.2) We note that the key difference between selection and learning lies in the cardinality of the policy class \Pi . In the selection problem, since \Pi is finite, we can exhaustively evaluate the performance of each policy. In the learning (optimization) problem, however, \Pi is typically a continuously parameterized class (e.g., neural networks), and thus solving it requires computational efficiency in the optimization process. In the literature, such requirement on the learning objective is called oracle efficiency ( Langford and Zhang, 2007 ; Wang et al., 2024 ) , meaning that the learning objective is optimizable efficiently assuming access to an optimization oracle. More concretely, we prefer objectives that are convex, or at least amenable to stochastic gradient-based optimization. Contributions. In this paper, we make two main contributions. First, we propose a novel OP selection method called PUB ( P essimism via semi- U nbounded-coin- B etting). PUB is an algorithm for computing a lower confidence bound (LCB) of any nonnegative random variable and is based on a variation of betting-based confidence bound ( Waudby-Smith and Ramdas, 2024 ; Orabona and Jun, 2024 ; Ryu and Bhatt, 2024 ) . By applying our new LCB to the importance-weighted rewards \{{\tilde{r}}_{t}^{\pi}\}_{t=1}^{n} (defined in Eq. ( 1.1 )) for each policy under consideration, we can establish a guarantee on the performance measure called offline regret (defined in Eq. ( 1.2 )), which is strictly tighter than existing works to our knowledge. We highlight two features in our guarantee. First, our regret bound scales with the standard deviation of \tilde{r}^{\pi} , significantly improving the prior art scaling with the raw second moment. Second, more crucially, we achieve the improved guarantee without any hyperparameter tuning . This is crucial in practice as tuning a parameter in the existing