Discovering, Learning and Exploiting Relevance

Cem Tekin, Mihaela van der SchaarNeurIPS 2014 · OpenReview

Overview

In many real-world decision-making scenarios—such as medical diagnosis or personalized recommendations—we are flooded with high-dimensional information. A doctor might have hundreds of data points on a patient, but the effectiveness of a specific drug might only depend on a single genetic marker. This paper introduces ORL-CF, a contextual multi-armed bandit algorithm that overcomes the "curse of dimensionality" by identifying which specific features (types) actually influence an action's reward. By learning this "relevance relation" online, the algorithm achieves a regret bound that is independent of the total number of context dimensions, making it highly effective for "big data" applications.

The Curse of Dimensionality in Contextual Bandits

In the language of machine learning, selecting actions based on incoming data is framed as a contextual multi-armed bandit (MAB) problem with a high-dimensional context vector ($D$). Standard algorithms for this problem suffer from the "curse of dimensionality": their performance loss (regret) grows exponentially with $D$.

This paper tackles the challenge of learning which dimensions are actually "relevant" to which actions. By doing so, a learner can ignore the noise of irrelevant data and converge on optimal decisions much faster.

The ORL-CF Algorithm

The authors propose the Online Relevance Learning with Controlled Feedback (ORL-CF) algorithm. Its core logic rests on three pillars:

  1. Adaptive Discretization: The algorithm avoids trying to learn the reward for every possible context value at once. Instead, it partitions the context space into smaller intervals (bins) that become more refined over time as more data arrives.
  2. Relevance Learning: For each action, the algorithm maintains reward estimates across different pairs of context types. It identifies the "relevant" type by looking for the dimension where the variation in reward estimates is consistent with the expected "smoothness" (Lipschitz continuity) of the reward function. If the reward varies wildly or randomly across a dimension, that dimension is likely irrelevant noise.
  3. Controlled Feedback: The algorithm alternates between exploration (choosing actions to learn the relevance relation and observing rewards) and exploitation (choosing the best-estimated action without needing to observe the reward). This "active learning" approach allows it to function efficiently even if observing a reward incurs a cost.

Key Insights and Ideas

The most significant insight of this work is that if the reward only depends on a small subset of features (in this case, a single "type" per action), the regret doesn't have to scale with the total number of features $D$. This effectively turns a "big data" problem into a series of manageable "small data" problems.

Illustration of different relevance relations mapping actions to context types.

The authors formalize the idea that for every action $a$, there is a mapping $\mathcal{R}(a)$ to a relevant context type. By treating this mapping as something to be discovered rather than assumed, the algorithm becomes much more flexible. Furthermore, the algorithm provides a crucial safety mechanism for fields like healthcare: a "suboptimality guarantee." It ensures that with high probability, it will never select an action that is significantly worse than the optimal one during its exploitation phases.

Key Results

The theoretical guarantees of ORL-CF are substantial:

  • Regret Bound: The algorithm achieves a regret of $\tilde{O}(T^\gamma)$, where $\gamma = 2/(1 + \sqrt{2}) \approx 0.828$.
  • Comparison to Baseline: Traditional contextual bandit algorithms that do not exploit relevance have a regret of $\tilde{O}(T^{(D+1)/(D+2)})$. As the number of dimensions $D$ increases, the baseline regret approaches linear (meaning the algorithm barely learns), while ORL-CF's regret remains constant regardless of $D$.
  • Active Learning Efficiency: Because the algorithm uses "controlled feedback," it can achieve the same order of regret even when there is a non-zero cost associated with observing a reward (e.g., the cost of a medical test).

Limitations and Future Work

While powerful, the current theoretical framework has a few limitations. The primary proof focuses on the case where the reward of an action depends on exactly one context type (a relevance function, as seen in the third panel of the figure above). While the authors provide a sketch for how to extend this to multiple relevant types (a broader relevance relation), the full theoretical heavy lifting for the general case is left for future work.

Additionally, the paper notes that if the relevance relation is linear (a weighted combination of types), ORL-CF might perform well but won't necessarily achieve sublinear regret relative to a benchmark that already knows the weights. Finally, the authors conjecture that the "true" lower bound for this problem might be $O(T^{3/4})$, suggesting there is still a small theoretical gap to close between their current results and the mathematical limit.

Summary updated

Abstract

In this paper we consider the problem of learning online what is the information to consider when making sequential decisions. We formalize this as a contextual multi-armed bandit problem where a high dimensional ($D$-dimensional) context vector arrives to a learner which needs to select an action to maximize its expected reward at each time step. Each dimension of the context vector is called a type. We assume that there exists an unknown relation between actions and types, called the relevance relation, such that the reward of an action only depends on the contexts of the relevant types. When the relation is a function, i.e., the reward of an action only depends on the context of a single type, and the expected reward of an action is Lipschitz continuous in the context of its relevant type, we propose an algorithm that achieves $\tilde{O}(T^{\gamma})$ regret with a high probability, where $\gamma=2/(1+\sqrt{2})$. Our algorithm achieves this by learning the unknown relevance relation, whereas prior contextual bandit algorithms that do not exploit the existence of a relevance relation will have $\tilde{O}(T^{(D+1)/(D+2)})$ regret. Our algorithm alternates between exploring and exploiting, it does not require reward observations in exploitations, and it guarantees with a high probability that actions with suboptimality greater than $\epsilon$ are never selected in exploitations. Our proposed method can be applied to a variety of learning applications including medical diagnosis, recommender systems, popularity prediction from social networks, network security etc., where at each instance of time vast amounts of different types of information are available to the decision maker, but the effect of an action depends only on a single type.
BibTeX
@inproceedings{tekin2014discovering,
  author = {Cem Tekin and Mihaela van der Schaar},
  title = {{Discovering, Learning and Exploiting Relevance}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=HyVtPvWd-B},
}
Figure