Computing an Efficient Exploration Basis for Learning with Univariate Polynomial Features

Chaitanya Amballa, Manu K. Gupta, Sanjay P. BhatAAAI 2021 · OpenReview

Abstract

Barycentric spanners have been used as an efficient exploration basis in online linear optimization problems in a bandit framework. We characterise the barycentric spanner for decision problems in which the cost (or reward) is a polynomial in a single decision variable. Our characterisation of the barycentric spanner is two-fold: we show that the barycentric spanner under a polynomial cost function is the unique solution to a set of nonlinear algebraic equations, as well as the solution to a convex optimization problem. We provide numerical results to show that our method computes the barycentric spanner for the polynomial case significantly faster than the only other known algorithm for the purpose. As an application, we consider a dynamic pricing problem in which the revenue is an unknown polynomial function of the price. We then empirically show that the use of a barycentric spanner to initialise the prior distribution in a Thompson sampling setting leads to lower cumulative regret as compared to standard initialisations. We also illustrate the importance of barycentric spanners in adversarial settings by showing, both theoretically and empirically, that a barycentric spanner achieves the minimax value in a static adversarial linear regression problem where the learner selects the training points while an adversary selects the testing points and controls the variance of the noise corrupting the training samples.

Introduction

In multi-armed bandit problems, a learner must navigate the fundamental trade-off between exploration (acquiring new information) and exploitation (maximizing rewards based on current knowledge). A critical component of effective exploration is the selection of a small set of "basis" points. If these points are chosen poorly, measurement noise can be significantly amplified, leading to suboptimal predictions across the decision space.

The optimal set of exploration points is known as a barycentric spanner. Formally, this is a subset of the decision space such that any other decision can be expressed as a linear combination of these basis points with coefficients in the range $[-1, 1]$. While theoretically robust, computing these spanners for general spaces is often computationally prohibitive. This research focuses on the common case where costs or rewards are univariate polynomials—a structure frequently encountered in applications like dynamic pricing.

Methodology

The authors investigate the decision set $D_n$, representing polynomial features up to degree $n$. They provide a dual characterization of the barycentric spanner for this set:

  1. Convex Optimization: The problem of finding the spanner is reformulated as maximizing the logarithm of the absolute determinant of a Vandermonde matrix. This objective is strongly concave, allowing for efficient resolution via standard interior-point methods.
  2. Nonlinear Equations: The spanner points are identified as the unique solution to a specific set of nonlinear algebraic equations, where the sum of the reciprocals of the differences between points must equal zero.

By leveraging the inherent symmetry of these points around the interval's midpoint, the computational complexity is halved. Furthermore, because the spanner is scale-invariant, it can be computed once for a given degree and mapped to any interval $[p_{min}, p_{max}]$.

Experimental Evaluation

The approach was evaluated using synthetic polynomial environments simulating dynamic pricing. The "true" demand curves were modeled as 2nd, 4th, or 9th-degree polynomials. The researchers also conducted robustness tests against model mismatch, such as assuming a 4th-degree polynomial when the underlying reality followed a 7th-degree polynomial or a radial basis function.

Key Results and Discussion

The proposed method demonstrates significant improvements in both computational efficiency and learning performance.

Computational Speed

For a polynomial of degree 20, the standard Awerbuch-Kleinberg (A-K) algorithm requires approximately 115 seconds. In contrast, the authors' reduced nonlinear equation method completes the task in just 0.024 seconds, representing a speedup of nearly 5,000x.

Regret Reduction

In dynamic pricing simulations, initializing Thompson Sampling with a barycentric spanner consistently outperformed standard baselines. This initialization leads to faster learning and significantly lower cumulative regret across various polynomial degrees.

Comparison of expected cumulative regret between the barycentric spanner and baseline method (1e5 scale).
Comparison of expected cumulative regret (1e4 scale) showing consistent performance gains.

Adversarial Robustness

Barycentric spanners were shown to be the "minimax" choice in adversarial regression. Even when an adversary selects the worst-case noise levels and test points, the learner's error remains minimized. Empirically, the barycentric spanner achieved a worst-case Mean Square Error (MSE) of 0.01, compared to 0.0291 for a "2-approximate" spanner.

Conclusion

This work transforms the geometric problem of finding an exploration basis into a well-defined optimization task, enabling massive computational speedups. While currently limited to univariate polynomials, the mathematical guarantees provide a strong foundation for future extensions. Future research will focus on generalizing these results to multivariate polynomials, which would expand applicability to complex multi-product pricing and high-dimensional bandit problems.

Summary updated

Abstract

Barycentric spanners have been used as an efficient exploration basis in online linear optimization problems in a bandit framework. We characterise the barycentric spanner for decision problems in which the cost (or reward) is a polynomial in a single decision variable. Our characterisation of the barycentric spanner is two-fold: we show that the barycentric spanner under a polynomial cost function is the unique solution to a set of nonlinear algebraic equations, as well as the solution to a convex optimization problem. We provide numerical results to show that our method computes the barycentric spanner for the polynomial case significantly faster than the only other known algorithm for the purpose. As an application, we consider a dynamic pricing problem in which the revenue is an unknown polynomial function of the price. We then empirically show that the use of a barycentric spanner to initialise the prior distribution in a Thompson sampling setting leads to lower cumulative regret as compared to standard initialisations. We also illustrate the importance of barycentric spanners in adversarial settings by showing, both theoretically and empirically, that a barycentric spanner achieves the minimax value in a static adversarial linear regression problem where the learner selects the training points while an adversary selects the testing points and controls the variance of the noise corrupting the training samples
BibTeX
@inproceedings{amballa2021computing,
  author = {Chaitanya Amballa and Manu K. Gupta and Sanjay P. Bhat},
  title = {{Computing an Efficient Exploration Basis for Learning with Univariate Polynomial Features}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=Qjt7Jq1bZF},
}
Figure