Showing posts with label Contextual Bandits. Show all posts
Showing posts with label Contextual Bandits. Show all posts

Sunday, November 13, 2022

The Decision-Estimation Coefficient

Essential Epistemology
This slide is from Leon Bottou's amazing ICML 2015 keynote. 
You should contemplate this image on a regular basis.

In the above slide Leon Bottou outlines three distinct, valid, and complementary ways of attempting to understand the world.  In AI all of these approaches are used, but with different emphasis as trends change.  Arguably, there was too much of the left hand side in the “if it's not convex it's crap” days, but then the deep learning revolution pushed many all the way to right.  In 2014 I asked a famous theoretician (who will remain anonymous) at a Q&A panel at ICML what he thought the role of theory was given recent developments, and he said “the role of theory is to predict experiments, but now we can just run experiments, so we don't need theory.”

Years later I now realize, the best theory doesn't predict experiments, it suggests them.  In other words, the best theory prompts ideas that otherwise would not be contemplated.  (Of course, there's still plenty of theory that attempts to explain experiments that are already run, and that's fine: the left column (“Exact Sciences”) of above image needs to digest the output of the other two columns.  This is necessary activity, but the real payoff comes when the left hand side suggests something that would have taken a very long time for the other two columns to consider.)

The Decision-Estimation coefficient (DEC) is amazingly good theory, because it suggests algorithm designs that otherwise would not be apparent: already I've published results on infinite action contextual bandits with arbitrary function classes, infinite action neural-bilinear contextual bandits, and risk-averse contextual bandits.  The last two are already implemented in Vowpal Wabbit and commercially available in Azure Personalizer Service.  In other words, these are not “COLT algorithms”, these are practical algorithms you can run on real problems.  (The first one, it works, but as stated in the original paper it doesn't generate causal data exhaust suitable for subsequent offline analysis.  We have a fix for this we will publish and then that version will go into the product.)  For risk-averse contextual bandits, I was confused for 18 months on how to achieve an online result (the exploration distribution affects the risk measure in a subtle way), and then Dylan Foster explained the DEC to me, and clarity soon followed.

Now I will pay it forward by explaining the DEC to you.

A Tale of Minnie and Max

The DEC is part of the rich tradition of minimax approaches to learning theory: excellent introductions are available from Lafferty et. al., Rakhlin and Sridharan, and Krishnamurthy.   For a more modern example, Duchi et. al. provide a minimax characterization of local differential privacy.   In classic minimax theory, one bounds the worst case value of a risk functional (i.e., something that says how good your decision rule is) subject to some constraints (e.g., local differential privacy).  The DEC is a bit different and fun because it operates as a machine learning reduction to regression, and therefore it bounds the worst case difference between performance on the original problem (“decision”) and the performance on the reduced problem (“estimation”). 

Basic Formulation

Here's one version suitable for contextual bandit algorithm design: $$ \text{DEC} = \min_P \max_{Q,f}\ \underbrace{\mathbb{E}_{a \sim P}\left[f(a)\right] - \mathbb{E}_{a \sim Q}\left[f(a)\right]}_{\text{CB regret}} - \gamma\ \underbrace{\mathbb{E}_{a \sim P}\left[ \left(f(a) - \hat{f}(a)\right)^2 \right]}_{\text{Estimation error}} $$ where
  • $P$ is Player's distribution over actions.  In the basic version, Player can pick any distribution over actions, but lately I've been having fun restricting the Player in various ways.
  • $Q$ is Nature's distribution over actions.  In the basic version, Nature can pick any distribution over actions, but constraining Nature is the basis for the smoothed infinite action result.
  • $f$ is Nature's choice of (expected) reward function.  By constraining Nature to pick from a limited complexity function class (e.g., neural-bilinear) you can get nontrivial bounds in infinite action spaces. 
  • $\hat{f}$ is the output of the regression oracle, i.e., our guess about what the true reward function is.
  • Estimation error here is measured in squared loss, but using different divergences gives different results, e.g., triangular discrimination yields an $L^*$ result for contextual bandits, and expectile loss yields a online risk averse contextual bandit. 
  • $\gamma$ can be interpreted as a learning rate which grows as the decision horizon (total number of rounds of decision making) grows.  It can also be interpreted as a Lagrange multiplier: in more recent (currently unpublished) formulations of the DEC the estimation error is constrained rather than subtracted.
  • You can add a context $x$ to all the components of the DEC (e.g., $\hat{f}(x, a)$), but it doesn't change anything since we evaluate the DEC example-by-example, so we elide it.


Closing the Loop

Let's understand why a DEC bound implies an effective reduction.  Informally, a bound on the DEC ensures that one of two things happens: 1) you do well on the original problem you care about or 2) you discover a mistake in your estimator.  Because we reduce to online no-regret learning and assume realizability, #2 eventually runs out of steam.  

More precisely, suppose we have a bound on the $\text{DEC} \leq C \gamma^{-\alpha}$.  After $T$ rounds we have $$\begin{aligned}\text{CB regret} &\leq T C \gamma^{-\alpha} + \gamma \sum_{t=1}^T \left(f_t(a) - \hat{f}_t(a)\right)^2 \\ &= T C \gamma^{-\alpha} + \gamma \text{Reg}(T) \\ &= C^{\frac{1}{1 + \alpha}} \alpha^{-\frac{\alpha}{1 + \alpha}} (1 + \alpha) T^{\frac{1}{1 + \alpha}} \text{Reg}(T)^{\frac{\alpha}{1 + \alpha}} \biggr|_{\gamma =\left(\frac{C T \alpha}{\text{Reg}(T)}\right)^{\frac{1}{1 + \alpha}}} \end{aligned}$$ and in particular 
  • (strongly observable) $\alpha = 1$ implies $\text{CB Regret} = O\left(\sqrt{T \text{Reg}(T)}\right)$ and $\gamma = O\left(\sqrt{\frac{T}{\text{Reg}(T)}}\right)$,
  • (weakly observable) $\alpha = \frac{1}{2}$ implies $\text{CB Regret} = O(\text{Reg}(T)^{1/3} T^{2/3})$ with $\gamma = O\left(\left(\frac{T}{\text{Reg}(T)}\right)^{2/3}\right)$,
  • (unobservable) $\alpha \to 0$ implies unbounded DEC and $\text{CB Regret} = O(T)$.
Of course, if $\text{Reg}(T) = T$ then you are hosed.  Fortunately for the version of the DEC presented here, with an arbitrary finite function class $\mathcal{F}$, we can use Vovk's aggregation algorithm to achieve $\text{Reg}(T) = O\left(\log \left| \mathcal{F} \right|\right)$, which yields the SquareCB result.  In general $\text{Reg}(T)$ will have $T$ dependence which degrades the overall CB regret bound.

Calling All Constructivists

Here's the important part: Foster et. al. show the DEC characterizes the statistical complexity of interactive decision making, but except for a few special cases, the reasoning is nonconstructive. More precisely, they swap the min and max to get an upper bound on the DEC objective value (aka Bayesian reasoning) which does not yield a constructive algorithm.  That means if you produce a constructive solution to the DEC for a particular scenario, you will have a novel algorithm which exhibits (near-)optimal minimax performance.  (Instance-dependent results are trickier, but possible.).

Consequently, I've been spending lots of time trying to find as many constructive solutions to the DEC as I can.  Now you know the secret so you can do the same.

Saturday, December 5, 2020

Distributionally Robust Contextual Bandit Learning

This blog post is about improved off-policy contextual bandit learning via distributional robustness. I'll provide some theoretical background and also outline the implementation in vowpal wabbit. Some of this material is in a NeurIPS expo talk video, and additional material is in the accepted paper.

Motivation

In off-policy learning in contextual bandits our goal is to produce the best policy possible from historical data, and we have no control over the historical logging policy which generated the data. (Note production systems that run in closed-loop configurations nonetheless are in practice doing off-policy learning because of delays between inference, training, and model update.) Off-policy learning reduces to optimization of a policy value estimator analogously to supervised learning; however the accuracy of policy value estimation depends upon the mismatch between the policy being evaluated and the policy that generated the data, and therefore can be quite different for different policies (unlike supervised learning, where the differences in estimator resolution across the hypothesis class are less pronounced in practice). To appreciate this effect consider the IPS policy value estimator, $$ \hat{V}(\pi; \mu) = \frac{1}{N} \sum_{n \in N} \frac{\pi(a_n|x_n)}{\mu(a_n|x_n)} r_n, $$ where $\mu$ is the historical policy, $\pi$ is the policy being estimated, and our historical data consists of tuples $\{ (x_n, a_n, r_n) \}$. The importance weight $\frac{\pi(a_n|x_n)}{\mu(a_n|x_n)}$ can be quite large if $\pi$ frequently takes an action that $\mu$ rarely takes, causing the estimator to be highly sensitive to a few examples with large importance weights. Even if we initialize learning with $\pi = \mu$, as optimization progresses $\pi$ will induce increasingly different distributions over actions than $\mu$ as the learning algorithm encounters rare events with high reward. To combat this overfitting technique we will introduce regularization.

Distributionally Robust Optimization

Distributionally robust optimization is a generic method for regularizing machine learning objectives. The basic idea is to consider the observed data as one possible distribution of data (the “empirical distribution”), and then to optimize a worst-case outcome over all distributions that are “sufficiently close” to the empirical distribution. In the case of IPS we can find the smallest policy value estimate over a set of distributions that are close in KL divergence to the empirical distribution, $$ \begin{alignat}{2} &\!\min_{P \in \Delta} & \qquad & \mathbb{E}_P\left[w r\right], \\ &\text{subject to} & & \mathbb{E}_P\left[w\right] = 1, \\ & & & \mathbb{E}_N \left[\log\left( P\right) \right] \geq \phi. \end{alignat} $$ where $w \doteq \frac{\pi(a|x)}{\mu(a|x)}$. It turns out you can do this cheaply (in the dual), and the value of $\phi$ can be computed from a desired asymptotic confidence level. These results follow from classic work in the field of Empirical Likelihood.

The above problem finds a lower bound; finding an upper bound is analogous, resulting in the confidence intervals from the paper:

Empirical Likelihood Confidence Intervals are tighter Gaussian intervals.  Not shown: coverage of Empirical Likelihood CIs is better calibrated than Binomial (Clopper-Pearson).


When we do distributionally robust optimization, we are actually optimizing the lower bound on the policy value. The green curve in the above plot is a Clopper-Pearson interval, which does have guaranteed coverage, but is so wide that optimizing the lower bound wouldn't do much until the amount of data is large. The tighter intervals generated by the blue Empirical Likelihood curve imply that lower bound optimization will induce an interesting policy ordering with only modest data.

In practice, even when the empirical mean (empirical IPS value) is fixed, the lower bound is:

  • smaller when the policy generates value via few events with importance weights much larger than 1 and many events with importance weights near zero; and
  • larger when the policy generates value via many events with importance weights near 1.
This is precisely the kind of regularization we desired. Intuitively, any estimator which is sensitive to a few of the observed examples (aka high leverage) will have a larger penalty because it is “cheap”, as measured by KL divergence, to reduce the probability of those points.

Implementation in Vowpal Wabbit

To activate the functionality, add the --cb_dro flag to your contextual bandit command line in VW. Note it only effects training, so if you are only predicting you will not see a difference. Hopefully with the default hyperparameters you will see an improvement in the quality of your learned policy, such as in this gist.

Internally VW is solving the lower bound optimization problem from above on every example. There are some modifications:

  1. As stated above this would be too expensive computationally, but switching from the KL divergence to the Cressie-Read power divergence allows us to derive a closed form solution which is fast to compute.
  2. As stated above the lower bound requires remembering all policy decisions over all time. Instead we accumulate the sufficient statistics for the Cressie-Read power divergence in $O(1)$ time and space.
  3. To track nonstationarity we use exponentially weighted moving averages of the sufficient statistics. The hyperparameter --cb_dro_tau specifies the decay time constant.
As always, YMMV.

Saturday, May 3, 2014

The Most Causal Observer

David K. Park recently had a guest post on Gelman's blog. You should read it. The tl;dr is ``Big Data is a Big Deal, but causality is important and not the same as prediction.''

I agree with the basic message: causality is important. As a bit of career advice, if you are just starting your career, focusing on causality would be a good idea. Almost never does one put together a predictive model for predictive purposes; rather, the point is to suggest an intervention. For example, why predict the fraud risk of a credit card transaction? Presumably the goal is to decline some transactions. When you do this, things change. Most simply, if you decline a transaction you do not learn about the counterfactual of what would have happened had you approved the transaction. Additional issues arise because of the adversarial nature of the problem, i.e., fraudsters will react to your model. Not paying attention to these effects will cause unintended consequences.

However I have reservations with the idea that ``creative humans who need to think very hard about a problem and the underlying mechanisms that drive those processes'' are necessarily required to ``fulfill the promise of Big Data''. When I read those words, I translate it as ``strong structural prior knowledge will have to be brought to bear to model causal relationships, despite the presence of large volumes of data.'' That statement appears to leave on the table the idea that Big Data, gathered by Big Experimentation systems, will be able to discover casual relationships in an agnostic fashion. Here ``agnostic'' basically means ``weak structural assumptions which are amenable to automation.'' Of course there are always assumptions, e.g., when doing Vapnik-style ERM, one makes an iid assumption about the data generating process. The question is whether humans and creativity will be required.

Perhaps a better statement would be ``creative humans will be required to fulfill the promise of Big Observational Data.'' I think this is true, and the social sciences have been working with observational data for a while, so they have relevant experience, insights, and training to which we should pay more attention. Furthermore another reasonable claim is that ``Big Data will be observational for the near future.'' Certainly it's easy to monitor a Twitter firehouse, whereas it is completely unclear to me how an experimentation platform would manipulate Twitter to determine causal relationships. Nonetheless I think that automated experimental design at a massive scale has enormous disruptive potential.

The main difference I'm positing is that Machine Learning will increasingly move from working with a pile of data generated by another process to driving the process that gathers the data. For computational advertising this is already the case: advertisements are placed by balancing exploitation (making money) and exploration (learning about what ads will do well under what conditions). Contextual bandit technology is already mature and Big Experimentation is not a myth, it happens every day. One could argue that advertising is a particular application vertical of such extreme economic importance that creative humans have worked out a structural model that allows for causal reasoning, c.f., Bottou et. al. I would say this is correct, but perhaps just an initial first step. For prediction we no longer have to do parametric modeling where the parameters are meaningful: nowadays we have lots of models with essentially nuisance parameters. Once we have systems that are gathering data and well as modeling it, will it be required to have strong structural models with meaningful parameters, or will there be some agnostic way of capturing a large class of casual relationships with enough data and experimentation?



Monday, June 25, 2012

Coactive Learning

Shivaswamy and Joachims have a paper called Online Structured Prediction via Coactive Learning at ICML 2012 this year. Joachims, of course, is associated with a classic line of research which I'll summarize thusly: attempting to impute absolute relevance scores from behavioral data exhaust is not effective, and that imputing relative preferences leveraging an attentional model (e.g., serial scan) is more effective. This is one of those ``deep tricks'' that you can carry with you into many different situations.

So the classic example is when you have a search engine result, and you get just one click at a particular position $p$, and your attentional model assumes that the user considered every result up to that position plus one more. Therefore the partial preferences $\forall x \in [1, p + 1], x \neq p: r_p > r_x$ are revealed and added to the (ranking) training set.

Later in my career I began to appreciate stochastic contextual bandits, specifically the importance of debiasing the historical state-action density in order to get consistent estimates. That left me with an inconsistency: on the one hand, optimizing a search engine with click feedback is definitely Learning Through Exploration, since you only get information about the relative preferences of (a subset of) the items presented. On the other hand I'm not attempting to debias the historical state-action density when I'm doing straight Joachims.

I was hoping this paper would resolve this difficulty for me. It did, but not in the way I expected; the contextual bandit literature is only referred to in the introduction for comparative purposes. Instead the authors make the following assumptions:
  1. User loss is convex in (linear) utility differences.
  2. Users only suggest improvements (i.e., user feedback always points ``downhill'').
  3. Users only suggest significant improvements (i.e., feedback states have a utility increment at least proportional to the increment to the optimum).
Under these circumstances it is sensible that a Perceptron-style algorithm achieves a good regret bound. The authors also explore relaxations of these assumptions (e.g., improvements are only significant in expectation, or feedback occasionally points downhill) and the resulting degradation of the regret guarantee.

I suspect the analysis does not look how I anticipated because, subject to the conditions of the previous paragraph, the user feedback can be chosen adversarially. Nonetheless it could be interesting to consider a ``contextual bandit style'' formulation, e.g., instead of learning the reward associated with the chosen arm, one learns the difference between the reward of the chosen arm and another arm. A good place to start would be the literature on contextual bandits with controlled side information, but a key difference here is that the user feedback is not under control of the algorithm.

Sunday, April 15, 2012

Interactive PAC

I recently was inspired to summarize progress in the application of PAC-style algorithm design for interactive settings, and ended up with this small table.
Probably Approximately Correct
Passive Batch Learning wrt draws of the data set IID Concentration
Passive Online Learning wrt draws of the data set Martingale (``Online to Batch'' conversion)
Active Online Learning wrt draws of the data set and sequence of label inspection decisions Martingale (custom?)
Contextual Bandits wrt draws of the data set and sequence of actions chosen Martingale (Freedman-style)
Two things jump out. The first is the versatility of martingales for taming interactive learning. How much further can this style of reasoning go? It'd be foolish to prognosticate with any certainty, but it feels like there is still some room to run. Ultimately there are the limits of the stochastic setting, of course: not all environments are well approximated as oblivious. So eventually we'll all be doing game theory, unless something like this has killed everybody. Before then, I worry about practically insurmountable sample complexity issues trying to tackle credit assignment problems in reinforcement learning. One can already see hints of this, e.g., worst-case instantaneous regret for agnostic stochastic contextual bandits indicates data requirements scale linearly with the number of possible actions. On the other hand, data volumes are scaling even faster than computation. If the relative growth continues indefinitely than computational complexity will trump sample complexity as an algorithmic design issue.

The second is the fundamental nature of online learning. In the 1990s you could be forgiven if (like me!) you thought of online learning as an implementation detail, a type of optimization strategy which was particularly good for the types of objective functions that arise in machine learning (I was totally unaware of prediction of individual sequences). With the benefit of hindsight, it is clear that online learning lends itself better to thinking about how information is revealed to (or collected by!) an algorithm over time, and that passive batch learning is more like a special case with particular implementation possibilities.

Wednesday, February 29, 2012

Active Learning and Contextual Bandits

Now that active learning is increasingly well understood, contextual bandits (CB) are a natural next focus of attention. My understanding of the current state of the art for stochastic CB is the following:
  1. We have computationally viable algorithms that can empirically perform well (e.g., Thompson sampling), but which do not provide strong agnostic theoretical guarantees. (That's a nice way of saying YMMV).
  2. We have algorithms that provide strong agnostic theoretical guarantees (e.g., Policy Elimination), but which are not computationally viable.
Progress here would be of more than theoretical interest: the stochastic CB setting describes a large number of problems I've attempted to solve over the years.

So I recently (naively?) thought ``hey, active learning algorithms are really good, and they are making a decision akin to explore/exploit, so maybe I can leverage that for a stochastic CB solution.'' It turns out this is not a good idea, but understanding why is interesting.

For illustration, consider a 2-armed contextual bandit with binary rewards (note: expected reward conditioned on the context is not necessarily binary; merely any particular realization of rewards is binary). In this case there is a natural correspondence between binary classifiers and stochastic CB policies. That suggests the following reduction of 2-armed stochastic CB to binary active learning.
Algorithm:Active Learning Stochastic Bandit
Two-armed contextual bandit algorithm leveraging active learning binary oracle $\mathcal{O}$.
  1. Obtain context $X_k$.
  2. Pass context $X_k$ as unlabeled data to $\mathcal{O}$, and receive the decision $Q_k \in \{ 0, 1 \}$ to query the label and predicted class $\hat Y_k \in \{ 0, 1 \}$.
  3. If $Q_k = 0$, pull arm $\hat Y_k$ and receive reward $R_{\hat Y_k} \in \{ 0, 1 \}$.
  4. If $Q_k = 1$,
    1. Choose $A_k \in \{ 0, 1 \}$ with equal probability (i.e., 50-50).
    2. Pull arm $A_k$ and observe reward $R_{A_k} \in \{ 0, 1 \}$.
    3. Let \[
      Y_k := \begin{cases} A_k & R_{A_k} = 1 \\ 1 - A_k & R_{A_k} = 0 \end{cases}.
      \]
    4. Pass $(X_k, Y_k)$ to $\mathcal{O}$ as is expected when $Q_k=1$.
The basic idea is the following: when the active learning algorithm requests the label, ``explore'' by randomizing the action; when the active learning algorithm does not request the label, ``exploit'' by performing the action that the underlying classifier wants. Problem solved!

Of course, not really. Let's analyze the algorithm. First, convince yourself that 0-1 classification loss on the data presented to the underlying oracle is proportional to the loss of the policy defined by the underlying classifier. Since active learning algorithms learn at essentially the same rate as passive learning algorithms (but without consuming all the labels), this means the ``exploitation policy'' will have an instantaneous regret of $O (\sqrt{\log(T) / T})$. However, in contextual bandits, it's the regret of the policy induced by the learning algorithm that matters. When the active learning algorithm requests the label, the regret is $O (1)$, and due to label complexity lower bounds for agnostic active learning, the label can be requested a constant fraction of the time; this implies the worst-case instantaneous regret of the policy induced by the learning algorithm is $O (1)$. That kind of regret bound is not going to you make you popular at the kind of parties where contextual bandit theory buffs hang out.

Now maybe in practice leveraging active learning for stochastic CB actually works well; certainly, if a suitable low-noise assumption is made, the label complexity of the active learning algorithm can be bounded and the overall regret can be made to look respectable. However this puts us back into the ``computationally viable heuristic'' zone, not the ``holy grail of agnostic stochastic CB algorithms'' zone.

Here's what's extra interesting: active learning appears fundamentally more difficult than stochastic CB. I say this because the label complexity lower bound problem does not plague direct solutions to stochastic CB. The amazing result from Dudik et. al. is that it is always possible to achieve $O (\sqrt{\log (T) / T})$ regret for the policy induced by the learning algorithm. Currently it is an open question how to do this in a computationally efficient manner, but already we can say the following: there is a big difference between having to choose whether to receive any reward information (active learning) versus being forced to only receive reward information about the action chosen (contextual bandits). In terms of the algorithm presented above, the problem is that anytime $Q_k = 0$, we ``throw away'' information; and leveraging that information is the difference between a constant worst-case instantaneous regret versus a worst-case instantaneous regret that decays over time.

Much thanks to John Langford for patiently explaining this to me. Now, I'm obsessed with contextual bandits! So far, naturally, my attempts to achieve $O (\sqrt{\log (T) / T})$ regret in the agnostic setting have not panned out, but it is really great fun.