# Contextual Inverse Optimization: Offline and Online Learning111An early
version of some of the results in present paper will appear in COLT’21 with
the title “Online Learning from Optimal Actions.” Only the abstract will
appear in the conference proceedings. We thank Alberto Seeger and the COLT
program committee members for valuable feedback.

Omar Besbes222Columbia Business School —<EMAIL_ADDRESS>Yuri
Fonseca333Columbia Business School —<EMAIL_ADDRESS>and Ilan
Lobel444NYU Stern School of Business —<EMAIL_ADDRESS>
(June 9, 2021)

###### Abstract

We study the problems of offline and online contextual optimization with
feedback information, where instead of observing the loss, we observe, after-
the-fact, the optimal action an oracle with full knowledge of the objective
function would have taken. We aim to minimize regret, which is defined as the
difference between our losses and the ones incurred by an all-knowing oracle.
In the offline setting, the decision-maker has information available from past
periods and needs to make one decision, while in the online setting, the
decision-maker optimizes decisions dynamically over time based a new set of
feasible actions and contextual functions in each period. For the offline
setting, we characterize the optimal minimax policy, establishing the
performance that can be achieved as a function of the underlying geometry of
the information induced by the data. In the online setting, we leverage this
geometric characterization to optimize the cumulative regret. We develop an
algorithm that yields the first regret bound for this problem that is
logarithmic in the time horizon.

Keywords: contextual optimization, online optimization, imitation learning,
inverse optimization, learning from revealed preferences, data-driven
decision-making.

##  1 Introduction

The two classical frameworks for studying decision-making with learning are
offline learning, where a decision-maker has access to a data set of contexts,
actions, and respective payoffs, and online learning, where a decision-maker
in each period is given a context, chooses an action and receives feedback in
the form of a payoff. Crucially, both of these frameworks assume the decision-
maker observes payoffs. However, there are important settings in which a
machine learning algorithm might not have access to the payoff from a
decision, but it does have access after-the-fact to the decision an expert
would have taken in that situation.

Learning problems of this form arise in a variety of settings. Consider a
medical machine learning system trying to learn to emulate a doctor’s approach
to treating a disease. The machine learning system can observe the patient
covariates (demographic information, medical history, blood work, etc.) and
needs to issue a treatment recommendation for a junior doctor to follow. A
senior doctor (an expert) is not available immediately, but is able to review
the treatment decision after-the-fact and input what his or her decision would
have been instead. That is, we have access to what an optimal solution would
have been to the problem we faced. However, we might never receive feedback on
whether a treatment worked, as patients might not inform the medical practice
what the outcome of the treatment was, or the feedback might be significantly
delayed in time. A similar scenario occurs if we are trying to build a system
to predict a user’s preferences. Most often, we can observe what the user
actually did after-the-fact, but we cannot observe the payoff to the user of a
particular decision. The same is true of some machine learning systems that
are designed to learn how to operate an autonomous system. We might be able to
learn by observing what a human driver (the expert) would have done, but we
might not have any payoff feedback. To formalize this class of problems, we
consider a general contextual optimization problem with both offline and an
online data.

For the offline setting, the decision-maker has access to data $\mathcal{D}$
of $N$ contextual optimization problems, each consisting of a set of feasible
actions $\mathcal{X}_{i}\subset\mathbb{R}^{n}$, a context function
$f_{i}:\mathbb{R}^{n}\to\mathbb{R}^{d}$ and an optimal solution
$x^{\star}_{i}\in\operatorname*{arg\,min}_{x\in\mathcal{X}_{i}}f(x)^{\prime}c^{\star}$
for some unknown vector $c^{\star}$. The challenge is to devise a good future
action based on the offline data. In particular, a key question pertains to
how “informative” the offline data is for future decision-making.

For the online setting, in each period $t$, the decision-maker receives a new
feasible set $\mathcal{X}_{t}\subseteq\mathbb{R}^{n}$ and a new context
function $f_{t}:\mathbb{R}^{n}\to\mathbb{R}^{d}$, and must select some action
$x_{t}\in\mathcal{X}_{t}$ in order to minimize an underlying objective
function $f_{t}(x_{t})^{\prime}c^{\star}$. As in the offline setting,
$c^{\star}$ is an unknown cost vector, which is only known to belong to some
initial knowledge set $C_{0}\subseteq\mathbb{R}^{d}$. The key question in this
setting is if the decision-maker can gain information about $c^{\star}$ over
time, and what type of performance can be achieved over time when we only
observe past optimal actions. Informally speaking, we are interested in
understanding how well can the decision-maker learn to mimic the expert.

###  1.1 Main contributions

In the offline setting, we do not make any distributional assumptions on the
contextual optimization problems. To the best of our knowledge, we establish
the first data-dependent minimax regret result for this problem. We do this by
exploiting the underlying geometry of the contextual optimization problem. For
the offline problem with data $\mathcal{D}$, we first characterize the set of
of cost vectors $C(\mathcal{D})$ that are consistent with the offline data and
establish that a key driver of performance is the uncertainty angle of the
information set $C(\mathcal{D})$, $\alpha(C(\mathcal{D}))$, which is a measure
of how large a revolution cone do we need to contain $C(\mathcal{D})$. The
axis of such a revolution cone is what’s called the circumcenter of
$C(\mathcal{D})$. We show in Theorem 1 that the offline policy that guarantees
an optimal worst-case regret bound for a new optimization problem is to treat
the circumcenter of $C(\mathcal{D})$ as if it were the true cost. In
particular, we show for the offline problem that regardless of the data size,
the worst-case future regret is given by $\sin\alpha(C(\mathcal{D}))$ if
$\alpha(C(\mathcal{D}))\leq\pi/2$ and 1 if $\alpha(C(\mathcal{D}))>\pi/2$.

For the online case, our first result is a negative one. In Theorem 2, we show
that a naïve application of the circumcenter policy fails, in the sense that
it may incur regret that is linear in the time horizon. Quite interestingly,
this policy may, in all periods, incur significant regret while also failing
to learn any meaningful new information on the underlying cost vector. This is
due to the potentially complex geometry of the knowledge set and highlights
how nature may counter the decision-maker and “gain” on both fronts: inflict
regret and limit information collection to ensure high future regret.

In turn, we develop an approach that leverages a series of ideas to exploit
the geometry of the problem while avoiding the pitfalls of the naïve (greedy)
circumcenter policy. We first assume that the initial knowledge set $C_{0}$
lives in a pointed cone. We regularize our knowledge sets by replacing them
with ellipsoidal cones that contain them. This regularization in conjunction
with an adjusted circumcenter policy introduces a trade-off for nature: now
nature will either inflict high regret or will not enable the decision-maker
to collect useful information on the cost vector, but can’t anymore achieve
both at the same time. In other words, the decision-maker can now indirectly
“force” nature to reveal information about the cost vector, a phenomenon we
coin “inverse exploration.” We then adapt the ellipsoid method from
optimization theory to deal with ellipsoidal cones instead and appropriately
update our regularized sets over time. The key to our algorithm’s performance
is to stop the ellipsoidal cones from becoming ill-conditioned, which we are
able to achieve by not performing ellipsoidal updates in periods in which the
decision is nearly optimal. In Theorem 3, we establish that the algorithm we
construct, properly tuned, achieves a worst-case regret bounded by
$\mathcal{O}(d^{2}\ln(T\tan\alpha(C_{0})))$.

The algorithm above was constructed assuming that the initial knowledge set
$C_{0}$ lived in a pointed cone, and enabled to highlight a first set of
phenomena at play in this class of problems. In Section 5, we drop this
assumption. To address this generalized version of the problem, we establish
that it is possible to always maintain a subspace such that the projection of
our knowledge set onto it has a bounded uncertainty angle (lives within a
pointed cone). We then extend our algorithm to have three different kinds of
periods: periods where our action is nearly optimal (no knowledge set update
is needed), periods where we perform an ellipsoidal cone update, and periods
where we add an extra dimension to our subspace. There are two new key steps
in this algorithm. First, we need to robustify the ellipsoidal cuts to account
for potential error introduced by the projection onto a subspace. Second, we
need to construct a new ellipsoidal cone every time we increase the dimension
of the subspace, and we need to argue that this new ellipsoidal cone has a
bounded uncertainty angle. For the constructed algorithm, properly tuned, we
are able to obtain a universal $\mathcal{O}(d^{4}\ln T)$ regret bound in
Theorem 4, regardless of the initial knowledge set, which is the main result
of this paper. For comparison, the prior state-of-the-art algorithms and
associated regret performance were presented in Bärmann et al. (2017), which
assume the context functions are linear, and achieve regret $O(\sqrt{T})$.

These results provide new achievability results for both the offline and the
online setting, but also novel algorithmic ideas to account for the special
nature of the feedback associated with optimal actions. We also hope that some
of these ideas can be useful in tackling more general versions of the problem,
such as problems with noise in the feedback.

Structure of the paper. Next, we position our paper in the broad literature.
We formulate the problem in Section 2. We analyze the offline setting in
Section 3 and the online setting in Sections 4 and 5. In Section 6, we discuss
open questions and possible extensions. We discuss connections to other models
in the literature in Appendix A and present the proofs of the results in the
paper in Appendix B.

###  1.2 Related Literature

The problem formulation we study allows us to encompass and relate to a
variety of problems studied earlier in the literature such as inverse
optimization, imitation learning and structured prediction problems with a
host of associated applications. We next broadly discuss how our work relates
to these streams of literature.

In the offline setting, inverse optimization typically refers to the problem
of finding an objective function given an optimal solution and a feasible set.
Ahuja and Orlin (2001) defined this problem early on and we refer the reader
to Chan et al. (2019) for recent developments. See also Keshavarz et al.
(2011), Bertsimas et al. (2015), Aswani et al. (2018), Thai and Bayen (2018).
Perhaps closest to our offline formulation is Esfahani et al. (2018), which
introduces a notion of regret to select among models in a distributionally
robust framework. We use the same loss function for our offline analysis. They
make distributional assumptions and work with strong convex nominal
optimization problems and with noisy observations and provide out-of-sample
guarantees for the Conditional Value-at-Risk of the regret. In the present
paper, we analyzes a more general nominal optimization problem, but without
noise, and provide a guarantee for the regret under an arbitrary new
optimization instance.

In the online setting, perhaps the closest paper to ours is Bärmann et al.
(2017), which studies an online version of inverse optimization. The key step
in Bärmann et al. (2017) is a reframing that allows the authors to leverage
online learning algorithms such as online gradient descent and exponential
weights updates, and prove a regret bound of $\mathcal{O}(\sqrt{T})$. In Ward
et al. (2019), the authors develop an online learning algorithm that is built
on exponential weights updates for dynamic scheduling with a regret guarantee
of $\mathcal{O}(\ln T\sqrt{T})$. Jabbari et al. (2016) studies a related
setting with a sequence of linear programming problems associated with the
behavior of a rational agent. Under the assumption that the true cost vector
is separated from all other candidate ones through the use of a precision
parameter, they show that the ellipsoid algorithm ensures that the number of
mistakes is bounded by a polynomial function of the precision parameter. In
contrast, we do not make any separation assumption and work with a continuum
of cost vector candidates. Also related is Dong et al. (2018) who analyze a
model with noisy observations of the expert’s actions while restricting
attention to a convex optimization problem, and again obtain
$\mathcal{O}(\sqrt{T})$ regret in terms of prediction accuracy. In a
different, but related class of problems, Amin et al. (2017) study regret in
an online problem in which the expert has access to a different type of
feedback: in addition to the expert’s action, the decision-maker is also
provided a binary feedback on the level of suboptimality of the decision which
is based on the true unknown set of parameters.

Relatedly, a class of applications in marketing is choice-based conjoint
analysis, where consumers are provided with a list of products to choose from
in a questionnaire. The answers are used to discover the consumer preferences.
In this setting, Toubia et al. (2007); Sauré and Vielma (2019) show how to
leverage polyhedral or ellipsoidal methods to select questionnaires that allow
one to recover the consumer utility function. In these, the decision-maker
chooses the optimization problems that will be solved by the consumer through
the sequence of questionnaires. In contrast, when interpreting our model in
this application, the optimization problems solved by the consumer can be
arbitrary and cannot be optimized by the decision-maker. Our online contextual
inverse optimization formulation is also related to studies on online
contextual pricing and contextual search (Roth et al. (2016), Lobel et al.
(2018), Paes Leme and Schneider (2018), Cohen et al. (2020), and Liu et al.
(2021)). While we are able to leverage some ideas from this literature such as
the use of ellipsoids and projected knowledge sets, we highlight, however,
that the nature of the problem studied here is substantially different from
the contextual pricing/search literature due to the nature of the feedback, as
there is no control in our setting on the feedback one sees. The recent
studies Feng et al. (2018) and Chen et al. (2021) study robust assortment and
price optimization based on revealed preferences associated with choice data.
Additional early works that focus on learning utility functions from revealed
preferences include Beigman and Vohra (2006), Zadimoghaddam and Roth (2012),
Balcan et al. (2014), Amin et al. (2015).

Imitation learning (Osa et al. (2018)) is also a framework where the goal is
to learn from optimal actions (or demonstrations). When inverse reinforcement
learning algorithms are used, the goal is to discover the reward function
associated with a Markov decision process (MDP) that describes the problem of
interest. In this stream, two important approaches are feature-matching
(Abbeel and Ng (2004)) and the maximum entropy method (Ziebart et al. (2008)).
In both frameworks, the reward function is described by an unknown linear
combination of a vector of known features. The goal is to learn the weights of
the reward function. In Ratliff et al. (2006), the authors use the Maximum
Margin Planning framework, also commonly used in structured prediction
problems that we describe below, for the online problem that consists of
solving a sequence of MDPs. The authors apply algorithmic techniques from the
online convex optimization literature to obtain a $\mathcal{O}(\sqrt{T})$
regret in terms of the prediction error. There, at each time $t$, the
decision-maker faces a different MDP. We refer to Arora and Doshi (2021) for a
review in algorithmic approaches to inverse reinforcement learning, and to
Bastani et al. (2021) for a recent application in the context of learning what
drives decisions of high performance workers in order to train and increase
performance of new or less experienced workers.

Finally, our work also relates to problems in structured prediction (Taskar et
al. (2005); Nowozin and Lampert (2011); Osokin et al. (2017)), where we
observe a set of covariates denoted as the input and another set of covariates
denoted as the output, and the goal is to discover a mapping from the inputs
to the outputs. Several approaches for solving structured prediction problems
assume an underlying optimization problem parametrized by the inputs, a stream
of methods usually referred to as “the argmax formulation.” The objective
function to be optimized can be seen as a score function, and the solution
that maximizes the score is given by the best possible prediction for the
output. An early and influential framework to solve the argmax formulation is
that of Maximum Margin Planning by Taskar et al. (2005). The Conditional
Random Field formulation for structured prediction introduced in Sutton and
McCallum (2006) can also be seen as an argmax formulation where the score
function is the likelihood function of the data observed.

##  2 Problem formulation

A contextual optimization problem will be defined by two objects: the first is
a feasible set of actions ${\cal X}$, which is a compact subset of an
Euclidean space $\mathbb{R}^{n}$, and the second is a context function
$f\in\mathcal{F}$, where $\mathcal{F}$ denotes the set of $L$-Lipschitz
continuous functions from $\mathbb{R}^{n}$ into $\mathbb{R}^{d}$. As a
normalization, we restrict our analysis to the case ${\cal X}\in\mathcal{B}$,
where $\mathcal{B}$ denotes the set of all compact subsets of $\mathbb{R}^{n}$
with diameter at most 1, i.e., $\sup_{x_{1},x_{2}\in{{\cal
X}_{t}}}\|x_{1}-x_{2}\|\leq 1$ (the operator $\|\cdot\|$ refers to the
Euclidean norm). Similarly, we also assume the Lipschitz constant $L$ from the
definition of the set of functions $\mathcal{F}$ is 1.

For a given cost vector $c$, feasible set ${\cal X}$ and context function $f$,
we introduce the following problem:

$\psi(c,{\cal X},f)=\operatorname*{arg\,min}_{x\in{\cal X}}f(x)^{\prime}c.$
(1)

We will refer to Problem (1) as the _forward (contextual) problem_. We do not
assume that the problem in Eq. (1) satisfies any additional structure such as
linearity or convexity, neither that its solution be unique.555The formulation
we consider is fairly general and encompasses various prototypical problems.
We discuss some examples in Appendix A.

The problem we will face in both the offline and online versions is one in
which the underlying cost vector $c^{\star}$ will be fixed but _unknown_
across problems. In turn, the decision-maker will be trying to optimize an
object related to the forward problem (or multiple instances of such a problem
in the online setting) but without knowledge of $c^{\star}$. Information about
$c^{\star}$ will come in the form of past optimal actions that would have been
chosen by an expert with knowledge of $c^{\star}$. We will assume that the
vector of unknown parameters $c^{\star}$ has dimension $d\geq 2$ as the case
$d=1$ case is trivial.

Throughout the paper, to lighten notation, we make the assumption that
$c^{\star}$ lives in a $d$-dimensional sphere with radius 1, which we denote
by $S^{d}$. However, we note that the analysis we develop does not rely on
this assumption and actually leads to performance bounds that can be
interpreted as being per unit of the true cost vector norm. We comment further
on this point following Theorem 4.

###  2.1 Offline setting

In the offline setting, we assume that the decision-maker has access to an
offline data set ${\cal D}$ consisting of $N$ past problem instances and
associated optimal decisions: $\mathcal{D}=\\{{\cal
X}_{i},f_{i},x^{\star}_{i}\\}_{i=1,\cdots,N}$. That is, for each observation
$i=1,\cdots,N$, we are given a set of feasible actions ${\cal
X}_{i}\in\mathcal{B}$, a context function $f_{i}\in\mathcal{F}$, and an
optimal action $x^{\star}_{i}\in\psi(c^{\star},{\cal X}_{i},f_{i})$.

Given a data set $\mathcal{D}$, the decision-maker can restrict the set of
cost vectors to a subset that is consistent with the optimal actions. In
particular, we define $C(\mathcal{D})$ to be the set of cost vectors
consistent with $\mathcal{D}$:

$\displaystyle C(\mathcal{D})=\\{c\in S^{d}:c^{\prime}f_{i}(x^{\star}_{i})\leq
c^{\prime}f_{i}(x),\;\forall\;x\in{\cal X}_{i},\;i=1,\cdots,N\\}.$ (2)

We will measure the performance of a policy through regret, which is the
difference between the decision-maker’s loss and the loss that could have been
achieved with knowledge of $c^{\star}$:

$\displaystyle\mathcal{R}^{\pi}\left(c^{\star},{\cal X},f\right)$
$\displaystyle=$
$\displaystyle\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}.$ (3)

The decision-maker selects a mapping $\pi$ from the data and the current
problem instance $({\cal X},f)$ that materializes, into a feasible action. We
let $\mathcal{P}$ denote the set of all such mappings. In particular, the
decision-maker aims to minimize the worst-case regret:

${\cal WCR}^{\pi}({\cal D})=\sup_{c^{\star}\in C(\mathcal{D}),~{}{\cal
X}\in\mathcal{B},~{}f\in\mathcal{F}}\mathcal{R}^{\pi}(c^{\star},{\cal X},f).$
(4)

###  2.2 Online setting

In the online setting, the time horizon is denoted by $T$. At every period
$t\in\\{1,...,T\\}$, the feasible actions set ${\cal X}_{t}\in\mathcal{B}$ and
the context function $f_{t}\in\mathcal{F}$ are revealed, and the decision-
maker needs to select an action $x_{t}$ in ${\cal X}_{t}$. Upon selecting an
action, the decision-maker incurs a cost given by
$f_{t}(x_{t})^{\prime}{c^{\star}}$, where $c^{\star}\in\mathbb{R}^{d}$ is
unknown to the decision-maker. In particular, the incurred cost
$f_{t}(x_{t})^{\prime}{c^{\star}}$ is never revealed to the decision-maker. At
the end of the period, the decision-maker observes an optimal action
$x_{t}^{\star}\in{\cal X}_{t}$. While the optimal action $x_{t}^{\star}$ is
revealed too late in period $t$ to be useful in that period, it potentially
allows the decision-maker to make better decisions in periods $t+1$ onwards
since it contains information about the cost vector ${c^{\star}}$.

We assume that initially the decision-maker knows only that $c^{\star}$
belongs to some initial knowledge set $C_{0}$. We assume that
$C_{0}\subset\mathbb{R}^{d}$ is a closed subset of $S^{d}$, the
$d$-dimensional sphere with unit radius. We also assume that $C_{0}$ is weakly
geodesically convex with respect to the sphere that contains it (that is, for
any two points in $C_{0}$, there exists a minimal-length arc over the surface
of $S^{d}$ connecting them that is fully contained in $C_{0}$). We let
$\mathcal{I}_{t}$ denote the information that is available when making a
decision in period $t$. In particular, ${\cal I}_{1}=\\{{\cal
X}_{1},f_{1}\\}$, and for all $t\geq 1$, $\mathcal{I}_{t+1}=\left\\{({\cal
X}_{s},f_{s},x_{s}^{\pi},x^{\star}_{s}):1\leq s\leq
t\right\\}~{}\cup~{}\\{{\cal X}_{t+1},f_{t+1}\\},$ where $x_{s}^{\pi}$ will be
defined shortly. We naturally focus on non-anticipatory policies (i.e.,
policies such that the action in period $t$ is measurable with respect to the
history $\mathcal{I}_{t}$). With some abuse of notation from the offline
setting, we let ${\mathcal{P}}$ denote this set of policies, and for any
policy $\pi\in\mathcal{P}$, we denote by $x_{t}^{\pi}$ the action it
prescribes in period $t$. Given the information collected up to time $t$, the
decision-maker can restrict the set of cost vectors to a subset that is
consistent with the optimal actions observed. In particular, we define
$C(\mathcal{I}_{t})$ to be the set of cost vectors consistent with
${\mathcal{I}}_{t}$:

$\displaystyle C(\mathcal{I}_{t})=\\{c\in
C_{0}:c^{\prime}f_{s}(x^{\star}_{s})\leq
c^{\prime}f_{s}(x),\;\forall\;x\in{\cal X}_{s},\;s=1,\cdots,t-1\\}.$ (5)

We will measure the performance of a policy through regret over $T$ periods,
which is the difference between the cumulative performance achieved and the
cumulative performance that could have been achieved with knowledge of
$c^{\star}$. For notational simplicity, we define
$\vec{\mathcal{X}}_{T}=({\cal X}_{1},...,{\cal X}_{T})$ and
$\vec{f}_{T}=(f_{1},...f_{T})$. For a given policy $\pi\in{\cal P}$, we define
the regret over $T$ time periods as:

$\displaystyle{\cal R}^{\pi}_{T}\left(c^{\star},\vec{\cal
X}_{T},\vec{f}_{T}\right)$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\bigl{(}f_{t}(x_{t}^{\pi})-f_{t}(x^{\star}_{t})\Bigr{)}^{\prime}c^{\star}.$
(6)

The decision-maker’s problem is to choose a policy $\pi\in\mathcal{P}$ in
order to minimize its cumulative regret assuming the cost vector $c^{\star}$,
the feasible sets $\vec{\mathcal{X}}_{T}$ and the context functions
$\vec{f}_{T}$ are chosen adversarially by nature. In other words, we want to
analyze the worst-case regret for a policy $\pi$:

$\displaystyle{\cal WCR}^{\pi}_{T}(C_{0})=\;\sup_{c^{\star}\in
C_{0},~{}\vec{\mathcal{X}}_{T}\in\mathcal{B}^{T},~{}\vec{f}_{T}\in\mathcal{F}^{T}}{\cal
R}^{\pi}_{T}\left(c^{\star},\vec{\cal X}_{T},\vec{f}_{T}\right).$ (7)

##  3 The Offline Problem

In this section, we focus on the offline problem: we start from a data set
$\mathcal{D}$ and aim to find a policy $\pi\in\mathcal{P}$ to minimize ${\cal
WCR}^{\pi}({\cal D})$, as defined in Eq. (4).

###  3.1 Proxy Policies

We begin our analysis by defining a class of policies that will play a central
role in our paper.

######  Definition 1 (Proxy policies).

We say $\pi\in\mathcal{P}$ is a _proxy policy_ if the action selected by the
policy $\pi$, $x^{\pi}$, is consistent with some cost vector $c^{\pi}$. In
particular, let $\psi$ be as defined in Eq. (1) and let $\mathcal{P}^{\prime}$
be the set of proxy policies defined as follows

${\cal P}^{\prime}=\>\Bigl{\\{}\pi\in{\cal P}:\mbox{ there exists some
}c^{\pi}\in S^{d}\mbox{ such that }x^{\pi}\in\psi(c^{\pi},{\cal X},f)\mbox{
for all }\mathcal{X}\in\mathcal{B}\mbox{ and }f\in\mathcal{F}\Bigr{\\}}.$

For an illustrative example of a policy in $\cal P^{\prime}$, suppose that
$\psi(c,{\cal X},f)$ corresponds to a linear program. If ${\cal X}$ is a
polytope, then every policy that chooses an action $x^{\pi}$ in the interior
of ${\cal X}$ cannot belong to $\cal P^{\prime}$, since the only cost vector
that makes an interior point optimal would be the origin, and the latter does
not belong to the unit sphere. In this case, a policy in ${\cal P}^{\prime}$
would only induce decisions corresponding to extreme points. Through proxy
policies, one can think about choosing costs vectors instead of actions of
possibly complicated instances ${\cal X}$ chosen by nature. This idea appears
in the literature and was used in problems such as structured prediction and
online inverse optimization (see, for instance, Taskar et al. (2005) and
Bärmann et al. (2017)).

Because a proxy policy is defined in terms of a cost vector, we will, with a
slight abuse of notation, refer to a proxy policy by its cost vector
$c^{\pi}$, and use $x^{\pi}$ to represent an action implied by $c^{\pi}$. This
representation creates a bit of ambiguity with respect to the value of
$x^{\pi}$ when the forward problem $\psi(c^{\pi},{\cal X},f)$ has multiple
optimal solutions. To address this ambiguity, we will consider the worst-case
choice of $x^{\pi}$ when introducing our loss function for proxy policy.
Recall that $c^{\star}$ is the true cost vector and $x^{\star}$ is an optimal
solution of the forward problem given $c^{\star}$. Then, the worst-case regret
for a policy $c^{\pi}$ given and a true cost vector $c^{\star}$ is given by:

$\displaystyle\mathcal{L}(c^{\pi},c^{\star})$ $\displaystyle=$
$\displaystyle\sup_{{x}^{\pi}\in\psi(c^{\pi},{\cal
X},f),\;\mathcal{X}\in\mathcal{B},\;f\in\mathcal{F}}~{}\Bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}.$
(8)

We define $\theta(\cdot,\cdot)$ to be the angle between two vectors, i.e.,
$\theta(c,\hat{c})=\arccos c^{\prime}\hat{c}/\|c\|\|\hat{c}\|$, with
$\theta(c,0)$ defined to be zero. Our next result shows that we can bound the
worst-case regret loss under policy $c^{\pi}$ using the angle between the
vectors $c^{\pi}$ and $c^{\star}$. This bound is tight in the sense that there
exists $\mathcal{X}$ and $f$ for which this bound holds with equality.

######  Lemma 1 (Realized worst-case regret).

Let $c^{\pi}$ be a policy in $\mathcal{P}^{\prime}$ and $c^{\star}$ be a cost
in $S^{d}$. Then,

$\displaystyle\mathcal{L}({c}^{\pi},c^{\star})$ $\displaystyle=$
$\displaystyle\begin{cases}\sin\theta(c^{\star},{c}^{\pi})&\mbox{if
}\theta(c^{\star},{c}^{\pi})<\pi/2,\\\ 1&\mbox{otherwise}.\end{cases}$

This lemma proves that if the angle between $c^{\pi}$ and $c^{\star}$ is
small, then the regret loss due to policy $c^{\pi}$ is small. If the angle is
$\pi/2$ or larger, then we risk incurring the maximal regret of 1. The proof
of the lemma is based on, first constructing a semi-definite relaxation of the
optimization problem from Eq. (8), then explicitly solving it, and finally
constructing an instance to show that the relaxation is tight.

Lemma 1 yields significant intuition: if ones wants to minimize the worst-case
regret for policies in $\cal P^{\prime}$, then one should select the proxy
cost vector $c^{\pi}$ that minimizes the worst-case angle with respect to the
unknown $c^{\star}$. We explore this idea in the next subsection.

###  3.2 The Uncertainty Angle and the Circumcenter

We now define two geometric objects that will be key to our analysis: the
uncertainty angle and the circumcenter of a set.

######  Definition 2 (Uncertainty angle and circumcenter).

Let $C$ be a nonempty set. We define the _uncertainty angle_ of $C$,
$\alpha(C)$, as

$\alpha(C)=\inf_{\hat{c}\in S^{d}}\sup_{c\in C}\theta(c,\hat{c}).$ (9)

If the infimum is attained, we call the minimizer of the equation above the
_circumcenter_ $\hat{c}(C)$ of set $C$.

To understand the notion of uncertainty angle, it is useful to think in terms
of revolution cones that contain the set $C$. A revolution cone
$K(\hat{c},\gamma)$ in $\mathbb{R}^{d}$ is defined by two objects, an axis
$\hat{c}\in S^{d}$ and an aperture angle $\gamma\in[0,\pi/2)$, and consists of
all points that are within an angle $\gamma$ of $\hat{c}$ (see Figure 1). If
we assume that $C$ is contained within a revolution cone and that
$K(\hat{c},\gamma)$ is the revolution cone with the smallest aperture angle
containing $C$, then $\alpha(C)=\gamma$. In this case, the vector $\hat{c}$ is
the circumcenter of the set $C$. In other words, the circumcenter $\hat{c}(C)$
of a set $C$ is the axis of the revolution cone containing it that has the
smallest aperture angle. Our definition of circumcenter is a slight
generalization of the one used in Henrion and Seeger (2010), which defines the
notion of the circumcenter of a cone (our definition applies to an arbitrary
nonempty set $C$). If $C$ is not contained in a revolution cone, $\alpha(C)$
could take values from $\pi/2$, if $C$ is a half-space, to $\pi$, if $C$ is
the full Euclidean space. When $\alpha(C)\geq\pi/2$, we will continue to refer
to a vector $\hat{c}(C)$ that minimizes Eq. (9) as the circumcenter of $C$,
even though $C$ is not contained in a revolution cone.

Figure 1: Set $C$ (intersection of the nonnegative orthant with the unit
sphere) and the smallest aperture-angle revolution cone (with axis
$\hat{c}(C)$) containing it. We increased the norm of $\hat{c}(C)$ for
illustrative purposes.

######  Lemma 2 (Existence and uniqueness of circumcenter).

Let $C$ be a nonempty set. There always exists a circumcenter $\hat{c}(C)\in
S^{d}$ that minimizes the right-hand side of Eq. (9). Furthermore, if
$C\setminus\\{0\\}$ is nonempty and $\alpha(C)<\pi/2$, then the circumcenter
is unique.

###  3.3 The Circumcenter Policy and the Offline Minimax Regret

The circumcenter of a set $C$ is the point that minimizes the angle of other
points in $C$ with respect to it. Therefore, a potentially good policy for the
offline problem is to treat the circumcenter of $C$ as a proxy cost. That is,
we choose the action $x^{\pi}\in\mathcal{X}$ by solving Eq. (1) with
$c=\hat{c}(C)$. We call this policy the _circumcenter policy_ and use the
representation $c^{\pi}=\hat{c}(C)$ to denote the proxy cost associated with
it.

######  Theorem 1 (Offline minimax regret).

Fix $\bar{\alpha}$ in $[0,\pi]$ and let $\Lambda(\bar{\alpha})$ denote the set
of all closed and weakly geodesically convex subsets of $S^{d}$ with
uncertainty angles bounded by $\bar{\alpha}$ (that is,
$\alpha(C)\leq\bar{\alpha}$ for all $C\in\Lambda(\bar{\alpha})$). We then
have:

$\sup_{\mathcal{D}:C(\mathcal{D})\in\Lambda(\bar{\alpha})}\>\inf_{\pi\in\mathcal{P}}\;{\cal
WCR}^{\pi}({\cal D})=\begin{cases}\sin\bar{\alpha}&\mbox{if
}\bar{\alpha}<\pi/2,\\\ 1&\mbox{otherwise}.\end{cases}$

Furthermore, the circumcenter policy achieves the bound above.

Theorem 1 characterizes the minimax regret as a function of the maximum
allowed uncertainty angle $\bar{\alpha}$. For any $\bar{\alpha}<\pi/2$, the
first sup (“worst-case” offline data) is a revolution cone with aperture angle
equal to $\bar{\alpha}$. In this case, the regret is equal to
$\sin\bar{\alpha}$. If $\bar{\alpha}\geq\pi/2$, then nature is able to cause
maximal regret (the maximal regret is 1 because we assumed that $c^{\star}$
has norm 1, the set $\mathcal{X}$ has diameter at most 1, and the context
function $f$ is 1-Lipschitz continuous). In particular, for the circumcenter
policy, the minimax regret for any offline data $\mathcal{D}$ is an instance-
dependent bound given by $\sin\alpha(C(\mathcal{D}))$ if
$\sin\alpha(C(\mathcal{D}))<\pi/2$, or $1$ otherwise. This result highlights
the driver of regret in offline problems and will be a crucial stepping stone
in the online setting.

##  4 The Online Setting: Initial Analysis and Intuition

The previous section constructs a policy called the circumcenter policy for
the offline problem that offers robust performance guarantees. The offline
learning problem is equivalent to the online learning problem with $T=1$, so
repeatedly applying the circumcenter policy will correspond to a greedy policy
in the online setting. In this section, we first explore the performance of
the greedy circumcenter policy and establish that it can fail, and then
establish how one may extend the circumcenter policy to a multi-period problem
if we assume that the initial knowledge set $C_{0}$ satisfies
$\alpha(C_{0})<\pi/2$, which we call the pointed case. This will allow us to
highlight a first set of core ideas and trade-offs at play in the online
setting that did not emerge in the offline setting. We later leverage these
ideas and the intuition from this section when we study the general case in
Section 5.

###  4.1 The Greedy Circumcenter Policy

Theorem 1 implies that the circumcenter policy is optimal in a worst-case
sense for the one-period problem. A natural candidate policy for the multi-
period problem is therefore to simply use the circumcenter policy in each
period, a policy we call the _greedy circumcenter policy_. Formally,

$\pi_{greedy}=\>\Bigl{\\{}x^{\pi}_{t}\in\psi(\hat{c}(C(\mathcal{I}_{t})),{\cal
X}_{t},f_{t})),\;\mbox{for every }t\leq T\Bigr{\\}},$

where, $C(\mathcal{I}_{t})=\\{c\in C_{0}:c^{\prime}f_{s}(x^{\star}_{s})\leq
c^{\prime}f_{s}(x),\;\forall\;x\in{\cal X}_{s},\;s=1,\cdots,t-1\\}$. This
policy might seem appealing due to its simplicity. However, the next
proposition shows that the worst-case regret incurred by the greedy
circumcenter policy is linear in the time horizon, even if the initial
knowledge set is pointed.

######  Theorem 2 (Insufficiency of the greedy circumcenter policy).

Fix $\bar{\alpha}\in(0,\pi/2)$ and let $\Lambda(\bar{\alpha})$ denote the set
of all closed and weakly geodesically convex subsets of $S^{d}$ with
uncertainty angles bounded by $\bar{\alpha}$ (that is,
$\alpha(C)\leq\bar{\alpha}$ for all $C\in\Lambda(\bar{\alpha})$). The worst-
case regret of the policy $\pi_{greedy}$ satisfies

$\sup_{C\in\Lambda(\bar{\alpha})}\>{\cal
WCR}^{\pi_{greedy}}_{T}(C)=\Omega(T).$

The proof of this proposition provides insights into the limitation of the
greedy circumcenter policy for the multi-period problem. We detail here the
key drivers of this linear regret through an example. Consider the example
presented in Figure 2 with initial knowledge set $C_{0}$. The associated
circumcenter $\hat{c}(C_{0})$ is on the boundary of the knowledge set (See
Figure 2(a)). In such a case, nature can construct adversarial instances
$\\{{\cal X}_{t},f_{t}\\}$ such that the decision-maker will not be able to
update meaningfully the knowledge set and, at the same time, incur positive
regret. Indeed, suppose that nature selects the identity as the context
function and a feasible set with two actions, $\mathcal{X}_{1}=\\{x_{1},0\\}$,
where $x_{1}$ is such that $\hat{c}(C_{0})^{\prime}x_{1}<0$ but
$\hat{c}(C_{0})^{\prime}x_{1}\approx 0$. (Figure 2(b)). Then the circumcenter
policy would prescribe to select $x_{1}$. Suppose that $c^{\star}$ is as
depicted in the figure. Then $x_{1}^{\star}=0$ and the updated information
after observing $x_{1}^{\star}$ would be minimal. Indeed, we would have
$C({\cal I}_{2})=C_{0}\cap\\{c^{\prime}x_{1}\geq 0\\}$, which would almost
coincide with $C_{0}$. We depict the updated set in Figure 2(c). If nature
repeatedly uses perturbations of such an instance, the cumulative regret will
be linear.

(a)

(b)

(c)

Figure 2: Example where the greedy policy fails. In $(a)$, we have the initial
knowledge set $C_{0}$ where the circumcenter lies in the border of $C_{0}$ and
achieves angle equal to $\pi/4$ with the extreme points. In $(b)$, the
optimization instance $f_{1}$ as the identity, $\mathcal{X}_{1}=\\{x_{1},0\\}$
and the true cost vector. In $(c)$ the updated set with minimal information
collection despite the high regret.

Note that the knowledge set at time $t+1$ can be represented by the
intersection of the knowledge set at time $t$ with all of the halfspaces that
characterize the optimality of $x_{t}^{\star}$, i.e.,

$C(\mathcal{I}_{t+1})=C(\mathcal{I}_{t})\cap\\{c\in\mathbb{R}^{d}:f_{t}(x^{\star}_{t})^{\prime}c\leq
f_{t}(x)^{\prime}c,\;\forall\;x\in{\cal X}_{t}\\}.$

That is, we update the knowledge set by intersecting it with a collection of
half-spaces. Thus, in general, the risk of the circumcenter being on the
boundary of the knowledge set is a significant one.

At a higher level, the greedy circumcenter policy suffers because it does not
introduce sufficient tension for nature’s problem. When nature tries to
counter the policy, it is able to both inflict high regret and limit
information collection for the decision-maker. This highlights that, in order
to counter nature, the decision-maker needs to design a policy that induces
nature to trade-off instantaneous regret performance and the prevention of
information collection. This would allow the decision-maker to accumulate
information over time. As the decision-maker can only learn indirectly by
forcing nature to reveal information about the nature of the costs, we refer
to this phenomenon as _inverse exploration_. In the next two subsections, we
describe the dynamics of information collection and how to avoid the pitfalls
of the greedy circumcenter policy presented in Theorem 2.

###  4.2 Information Collection and Knowledge Set Update

At each period, after observing the expert’s action $x_{t}^{\star}$, the
knowledge set update corresponds to adding constraints
$(f_{t}(x)-f_{t}(x^{\star}))^{\prime}c\geq 0$ for each $x\in\mathcal{X}_{t}$.
Let us define:

$\delta_{t}(x)=\frac{f_{t}(x)-f_{t}(x^{\star}_{t})}{\|f_{t}(x)-f_{t}(x^{\star}_{t})\|},$

with $\delta_{t}(x)=0$ if $f_{t}(x)-f_{t}(x^{\star}_{t})=0$. Then, the full
update constraints can be rewritten as $\delta_{t}(x)^{\prime}c\geq 0$ for all
$x\in\mathcal{X}_{t}$. This is a fairly complicated procedure since the object
$\\{c\in\mathbb{R}^{d}:\delta_{t}(x)\geq 0,\;\forall\;x\in{\cal X}_{t}\\}$ is
the intersection of potentially infinitely many halfspaces. Therefore, instead
of focusing on all of the halfspaces, we will focus only on one specific
halfspace, a procedure we will call the relaxed update. Denote
$\delta^{\pi}_{t}=\delta_{t}(x^{\pi}_{t})$ as the _effective difference_ ,
which is the vector associated with the action $x_{t}^{\pi}$ chosen at period
$t$. We use the name effective difference because each period regret is simply
the inner product of $\delta^{\pi}_{t}$ with $c^{\star}$ (up to the norm of
$\delta_{t}^{\pi}$, which is bounded by 1). We will define the relaxed update
to be equal to

$C(\mathcal{I}_{t})\cap\\{c\in\mathbb{R}^{d}:\;{\delta^{\pi}_{t}}^{\prime}c\geq
0\\}.$ (10)

That is, in the relaxed update we include only one new constraint at time $t$,
the one associated with what we call the effective difference. The effective
difference satisfies two important inequalities that will be crucial in order
to understand how inverse exploration manifests itself. First,
${\delta_{t}^{\pi}}^{\prime}c^{\star}\geq 0$ since $x_{t}^{\star}$ is optimal
with respect to $c^{\star}$. Second, for any proxy policy $c^{\pi}_{t}$, we
have that $x_{t}^{\pi}$ is optimal with respect to $c_{t}^{\pi}$, which
implies that $f_{t}(x_{t}^{\pi})^{\prime}c^{\pi}_{t}\leq
f_{t}(x)^{\prime}c_{t}^{\pi}$ for all $x\in{\cal X}_{t}$, and thus,
${\delta_{t}^{\pi}}^{\prime}c^{\pi}_{t}\leq 0$. In turn, we have the following
implication on the link between $c^{\pi}_{t}$ and $C(\mathcal{I}_{t+1})$ if
${\delta_{t}^{\pi}}\neq 0$:

${\delta_{t}^{\pi}}^{\prime}c^{\pi}_{t}\leq 0\mbox{ and
}{\delta_{t}^{\pi}}^{\prime}c^{\star}\geq 0,\mbox{ for }c^{\star}\in
C(\mathcal{I}_{t})\implies c_{t}^{\pi}\notin\mbox{int}(C(\mathcal{I}_{t+1})).$
(11)

The two conditions in Eq. (11) imply that if $c_{t}^{\pi}$ is “sufficiently”
in the relative interior of $C(\mathcal{I}_{t})$, only two cases can happen:
either we are able to remove a sufficient mass of candidates when updating
$C(\mathcal{I}_{t+1})$, or $\delta_{t}^{\pi}=0$, implying no regret.
Therefore, there exists a tension in this problem between minimizing
instantaneous regret (which is achieved via the circumcenter policy) and
gaining more information (which is achieved by selecting a proxy cost
sufficiently in the interior of the knowledge set).

######  Remark 1 (nature of the feedback).

Here we highlight an important and fundamental difference from the contextual
search literature discussed in Subsection 1.2. There, the vector
$\delta_{t}^{\pi}$ (commonly denoted as the contextual information) would have
been known before choosing the proxy cost $c_{t}^{\pi}$, whereas in our case,
$\delta_{t}^{\pi}$ materializes only in the end of the period. As a result,
here we can only indirectly affect it by our choice of proxy cost
$c_{t}^{\pi}$.

Next, we show that if one starts with an uncertainty set that lives in a
pointed cone, then, it is possible to conduct inverse exploration and “force”
nature to trade-off between inflicting regret and limiting information
collection. Our strategy is to replace the knowledge sets in our algorithm
with regularized supersets that contain $C(\mathcal{I}_{t})$. These supersets
will ensure that useful information is collected over time despite us using a
greedy approach (choosing the circumcenter of the superset as a proxy cost),
which will automatically balance the trade-off between instantaneous
performance and information gain.

###  4.3 Ellipsoidal Cones

We replace the knowledge sets with ellipsoidal cones, which are better-behaved
objects and guarantee the circumcenter is always in the interior of the
superset. These supersets will allow us to leverage the powerful machinery
from the ellipsoid method (Khachiyan, 1979) in order to update the knowledge
set every time that we collect a new effective difference.

In Figure 3, $E$ is an ellipsoidal cone that contains the initial knowledge
set that was used in Figure 2. $C_{0}$ is a “bad” instance that can lead to a
linear regret with the greedy circumcenter policy since its circumcenter is in
the border of the set. $\hat{c}(E)$ is the circumcenter of the ellipsoidal
cone that contains $C_{0}$ and is “sufficiently” close to the original
circumcenter but also sufficiently in the relative interior of $C_{0}$ to
ensure inverse exploration.

Figure 3: Example of an ellipsoidal cone $E$ that contains an initial
knowledge set $C_{0}$, including the circumcenter of $C_{0}$, $E$ and a true
cost candidate. The vectors were rescaled for illustrative purposes.

We will need notation to refer to specific components of a vector
$c\in\mathbb{R}^{d}$. We use $c_{[i:j]}$ to denote the entries $i,...,j$ of
the vector $c$. Before we present the general definition of an ellipsoidal
cone, we introduce the notion of a standard-position ellipsoidal cone, which
is one where the axis of the cone is the canonical vector $e_{1}$, and the
eigenvectors of the generating ellipsoid are the canonical vectors
$e_{2}$,…,$e_{d}$. Let $\mathbb{D}^{d}_{++}$ be the set of $d$-dimensional
positive-definite diagonal matrices.

######  Definition 3 (Standard-position ellipsoidal cone).

We say that a set $E(W)\subseteq\mathbb{R}^{d}$ is a _standard-position
ellipsoidal cone_ if there exists a matrix $W\in\mathbb{D}^{d-1}_{++}$ such
that

$E(W)=\left\\{c\in\mathbb{R}_{+}\times\mathbb{R}^{d-1}:\;c_{[2:d]}^{\prime}W^{-1}c_{[2:d]}\leq
c_{[1]}^{2}\right\\}.$

The definition above implies that $E(W)$ is contained in the halfspace
$\\{c\in\mathbb{R}^{d}:\;e_{1}^{\prime}c\geq 0\\}$ and that its circumcenter
$\hat{c}(W)$ is equal to $e_{1}$. We obtain other ellipsoidal cones via
rotation.

######  Definition 4 (Ellipsoidal cone).

We say that a set $E(W,U)\subseteq\mathbb{R}^{d}$ is an _ellipsoidal cone_ if
there exists an orthonormal matrix $U\in\mathbb{R}^{d}\times\mathbb{R}^{d}$
and a standard-position ellipsoidal cone $E(W)$ such that $c\in E(W,U)\iff
U^{-1}c\in E(W).$

Since the uncertainty angle is not affected by orthonormal transformations, it
follows that, for an ellipsoidal cone $E(W,U)$, the circumcenter is given by
$Ue_{1}$, i.e., $\hat{c}(E(W,U))=Ue_{1}$.

Cone Updates. A key advantage of keeping track of the knowledge superset as an
ellipsoidal cone is that we can build on the ellipsoid method to update our
knowledge superset over time. In the classic ellipsoid method, one starts each
period with an ellipsoidal feasible set, finds a cut through the center of the
ellipsoid, removing half of the potential solutions, and then one constructs
the Löwner-John ellipsoid of the remaining half-ellipsoid, where the Löwner-
John ellipsoid of a convex set refers to the smallest volume ellipsoid that
contains it. The key argument in the ellipsoid method is that this process
reduces the volume of the ellipsoid by $e^{-1/2d}$ at each time step if we are
working in a $d$-dimensional space (Grötschel et al., 1993, Lemma 3.1.28, page
74). We will now argue that we can extend this method to work with ellipsoidal
cones and that we obtain similar volume reduction guarantees.

(a) Ellipsoidal cone intersected with the hyperplane defined by
$\hat{c}(E(W_{t},U_{t}))=e_{1}$ and the effective difference projected onto
the hyperplane. The updated ellipsoid (in black) remains on the hyperplane and
is defined by the center $a$ and the matrix $N$ calculated with the standard
ellipsoid method.

(b) Cross-section of the updated ellipsoidal cone. Note that the vector
$(1,a)$ obtained directly by standard ellipsoid method does not give us the
circumcenter of the new updated ellipsoidal cone, which is computed instead
via spectral decomposition.

Figure 4: The steps required to perform an update of the ellipsoidal cone.

We now proceed to describe our cone-update algorithm. Intuitively, our cone-
update algorithm can be understood as a two-step procedure. We start by
performing one step of the ellipsoid method using the ellipsoid obtained by
the intersection of $E(W_{t},U_{t})$ with an appropriate hyperplane defined by
its circumcenter $\hat{c}(E(W_{t},U_{t}))$ (see Figure 4(a)). In the second
step, we calculate the circumcenter of the new ellipsoidal cone. As we
illustrate in Figure 4(b), the circumcenter of the new ellipsoidal cone is not
in general given by the center of the updated ellipsoid. Instead, we need to
compute the spectral decomposition of an appropriate matrix to determine it.
We call this algorithm ConeUpdate and it is fully laid out in Algorithm 1. As
specified, it includes more parameters than we need here. Those extra
parameters ($\eta$, $B$, and $p$) will only be needed when we get to Section
5.

input : Matrices $W,U$, projected vector $\delta$, margin $\eta$, basis $B$,
dimension $p$.

$\bar{\delta}=U^{-1}B\delta$;

$\beta\leftarrow-\frac{\eta}{\sqrt{{\bar{\delta}}^{\prime}_{[2:p]}W{\bar{\delta}}_{[2:p]}}}$,
$b\leftarrow\frac{W{\bar{\delta}}_{[2:p]}}{\sqrt{{{\bar{\delta}}}^{\prime}_{[2:p]}W{\delta}_{[2:p]}}}$,
$a\leftarrow\frac{1+(p-1)\beta}{p}b$;

$N\leftarrow\frac{(p-1)^{2}}{(p-1)^{2}-1}(1-\beta^{2})(W-\frac{2(1+(p-1)\beta)}{p(1+\beta)}bb^{\prime})$;

$M\leftarrow\begin{pmatrix}1&a^{\prime}\\\ a&aa^{\prime}-N\end{pmatrix}$;

Let $V^{\prime}\Lambda V$ denote the spectral decomposition of $M$;

$\widetilde{U}\leftarrow UV$;

Set $\widetilde{W}_{i,i}\leftarrow\lambda_{i}(N)$, $i=1,\cdots,p-1,$ where
$\lambda_{i}(N)$ are arranged in nondecreasing order;

output : $\widetilde{W},\widetilde{U}$.

Algorithm 1 ConeUpdate

Lemma 3 will formalize two properties of ConeUpdate. It shows that after
collecting an effective difference, we can fit another ellipsoidal cone that
contains the remaining set of feasible costs and, furthermore, we can
guarantee a reduction on the product of the eigenvalues with the same rate as
obtained by the ellipsoid method in $(d-1)$ dimensions. We let
$\lambda_{i}(W)$ denote the $i^{th}$ eigenvalue of a matrix $W$ and
$I_{d}\in\mathbb{D}_{++}^{d}$ denote the identity matrix.

######  Lemma 3 (Ellipsoidal cone updates).

Suppose we run algorithm _ConeUpdate_ with inputs $W_{t}$, $U_{t}$,
$\delta_{t}^{\pi}$, $\eta=0$, $B=I_{d}$, and $p=d$. Assume that
$C(\mathcal{I}_{t})\subseteq E(W_{t},U_{t})$. Then,
$C(\mathcal{I}_{t+1})\subseteq
E(W_{t},U_{t})\cap\\{c\in\mathbb{R}^{d}:\;{\delta_{t}^{\pi}}^{\prime}c\geq
0\\}\subseteq E(W_{t+1},U_{t+1})$. Moreover,
$\prod_{i=1}^{d-1}\lambda_{i}(W_{t+1})\leq
e^{-1/(d-1)}\prod_{i=1}^{d-1}\lambda_{i}(W_{t})$.

###  4.4 The Algorithm for the Pointed Case

We now explore the architecture for our algorithm. We start by replacing our
initial knowledge set with a revolution cone that contains it (which is
possible since we assume $\alpha(C_{0})<\pi/2$ for now), and then at each
period $t$, we choose the circumcenter of the ellipsoidal cone
$E(W_{t},U_{t})$ as our proxy cost. We use the algorithm ConeUpdate whenever
we want to update our knowledge superset. The last missing step is to propose
a rule for deciding when our algorithm should perform a ConeUpdate.

Recall that the uncertainty angle of the knowledge set is key for bounding the
one-period regret. Proposition 1 relates the uncertainty angle of an
ellipsoidal cone $E(W,U)$ to the matrix $W$.

######  Proposition 1 (Uncertainty angle of ellipsoidal cones).

Let $W\in\mathbb{D}^{d-1}_{++}$ and let $\lambda_{max}(W)$ denote the largest
eigenvalue of the matrix $W$. Then,
$\alpha(E(W,U))=\arctan\sqrt{\lambda_{max}(W)}$.

Proposition 1, together with Theorem 1, highlight the need to control not just
the product of the eigenvalues over time, but also the value of the largest
eigenvalue of $W_{t}$. Controlling the largest eigenvalue is challenging
because of a quirk of the ellipsoid method. When we perform an update step in
ConeUpdate, we sometimes create an ellipsoid that has a larger eigenvalue than
any eigenvalue in the original ellipsoid (this is discussed, for example, in
Cohen et al. (2020, Figure 6)). Geometrically, the ellipsoid method runs the
risk of creating ellipsoids that are “long and skinny” (in technical terms,
ill-conditioned). If the ellipsoid has at least one large eigenvalue, then
Proposition 1 shows its uncertainty angle will be large.

The key to completing our pointed-case algorithm will be to use cone-updates
sparingly. Instead of updating our ellipsoidal cone after computing every
effective difference, we will only update the ellipsoidal cone if we made a
“substantial” mistake, where the threshold for determining whether a mistake
is substantial is described by a new parameter $\epsilon>0$. Let
$\bar{\delta}_{t}$ be the rotated effective difference so that we are working
in standard position, i.e., $\bar{\delta}_{t}=U_{t}^{-1}\delta_{t}^{\pi}$. At
every time $t$, we do not update the ellipsoidal cone if:

${\bar{\delta}}^{\prime}_{t,[2:d]}W_{t}{\bar{\delta}}_{t,[2:d]}\leq\epsilon^{2}.$
(12)

The next result establishes that such periods lead to low regret.

######  Lemma 4 (Sufficiency for one-period low regret).

Assume that $C(\mathcal{I}_{t})\subseteq E(W_{t},U_{t})$. Suppose that Eq.
(12) holds, then the one-period regret in period $t$ is upper bounded by
$\epsilon$.

In other words, whenever Eq. (12) holds, we have a certificate to ensure low
regret in period $t$ and updating the ellipsoidal cone with the information
provided by the current effective difference would risk causing some of the
larger eigenvalues to grow for very little benefit.

Therefore, we say period $t$ is a _cone-update period_ if
${\bar{\delta}}^{\prime}_{t,[2:d]}W_{t}\bar{\delta}_{t,[2:d]}>\epsilon^{2}$.
Let us denote the number of cone-update periods by

$I^{\pi}_{T}=\sum_{t=1}^{T}\mathbf{1}\\{{\bar{\delta}}^{\prime}_{t,[2:d]}W_{t}\bar{\delta}_{t,[2:d]}>\epsilon^{2}\\}.$

If the period is not an update one, we call it a _low-regret period_ since the
regret in that period is upper bounded by $\epsilon$. The next lemma argues
that, since updates only occur when Eq. (12) is violated, the maximum
eigenvalue of the ellipsoid is bounded as function of $I_{T}^{\pi}$.

######  Lemma 5 (Largest eigenvalue under $\epsilon$-update).

Suppose $\lambda_{1}(W_{1})>\left(\frac{\epsilon}{10(d-1)}\right)^{2}$. Then,
after $I^{\pi}_{T}$ updates, we have that

$\lambda_{max}(W_{t})\leq\left(\frac{10d}{\epsilon}\right)^{2(d-2)}\left(\lambda_{max}(W_{1})\right)^{d-1}e^{-\frac{I_{T}^{\pi}}{(d-1)}},$

where $\lambda_{max}(W_{1})$ denotes the largest eigenvalue of the initial
ellipsoidal cone $E(W_{1},U_{1})$. If
$\lambda_{1}(W_{1})\leq\left(\frac{\epsilon}{10(d-1)}\right)^{2}$, then
$I^{\pi}_{T}=0$ and the per period regret is bounded above by $\epsilon$ for
all periods.

The main algorithm of the current section, EllipsoidalCones, chooses the
circumcenter of the ellipsoid as the proxy cost in each period, and it updates
the ellipsoid only when Eq. (12) is violated. A full specification is
presented in Algorithm 2.

input : time horizon $T$, dimension $d$, initial knowledge set $C_{0}$,
parameter $\epsilon$.

Rotate $C_{0}$ to place the circumcenter of $C_{0}$ at $e_{1}$;

Construct a revolution cone containing $C_{0}$:
$\left(W_{1}\leftarrow\tan^{2}\alpha(C_{0})I_{d-1},~{}U_{1}\leftarrow
I_{d-1}\right)$;

for  _$1\leq t\leq T$_ do

Set $c_{t}^{\pi}\leftarrow U_{t}e_{1}$,
$\bar{\delta}=U^{-1}_{t}\delta_{t}^{\pi}$;

Choose action $x^{\pi}_{t}\in\psi(c^{\pi}_{t},{\cal X}_{t},f_{t})$;

Observe $x^{\star}_{t}$;

Set
$\delta_{t}^{\pi}\leftarrow\frac{f_{t}(x^{\pi}_{t})-f_{t}(x^{\star}_{t})}{\|f_{t}(x^{\pi}_{t})-f_{t}(x^{\star}_{t})\|}$;

if
_${\bar{\delta}}^{\prime}_{[2:d]}W_{t}{\bar{\delta}}_{[2:d]}\leq\epsilon^{2}$_
then

$W_{t+1},U_{t+1}\leftarrow W_{t},U_{t}$;

else

$W_{t+1},U_{t+1}\leftarrow\mbox{{ConeUpdate}}(W_{t},U_{t},\delta_{t}^{\pi},0,I_{d},d)$;

end if

end for

Algorithm 2 EllipsoidalCones

We are now ready to present its performance.

######  Theorem 3 (Regret for pointed case).

Set $\epsilon=d/T$ in _EllipsoidalCones_. Consider any $C_{0}$ with
$\alpha(C_{0})<\pi/2$. If $\alpha(C_{0})>\arctan({d}/{T})$, then the regret is
bounded as follows:

${\cal
WCR}^{\pi}_{T}\left(C_{0}\right)\leq\mathcal{O}\left(d^{2}\ln(T\tan\alpha(C_{0}))\right).$

If $\alpha(C_{0})\leq\arctan({d}/{T})$, then the regret is bounded by
$\mathcal{O}(d)$. This algorithm runs in polynomial time in $d$ and $T$.

This result says that if the uncertainty angle of the initial knowledge set is
bounded, then we can obtain a strong performance guarantee. We have
constructed a policy that avoids the pitfalls of the greedy circumcenter
policy and yields logarithmic regret in the time horizon. The key to this
result was to exploit the underlying geometry of the problem at hand and the
regularization of the knowledge sets that enabled the decision-maker to force
inverse exploration for nature. These ideas will be crucial when we relax the
assumption of pointedness of the initial knowledge set in the next section.

We remark here that the worst-case regret admits a dependence $d^{2}$. It is
possible that the dimension dependence might still be improved; the $d^{2}$
term in the regret bound is a consequence of our choice of using ellipsoidal
cones as supersets. It is possible that an alternative superset that fits the
knowledge set more tightly might lead to a better dependence on $d$.

##  5 The Online Setting: General Case

We will now drop the assumption that the initial knowledge set lies within a
pointed cone ($\alpha(C_{0})<\pi/2$) and construct an algorithm,
ProjectedCones, to solve the general case. In this general setting, one key
idea will be the following. At each period $t$, if $C(\mathcal{I}_{t})$ does
not have an uncertainty angle less than $\pi/2$, we will search for a linear
subspace, denoted by $\Delta_{t}$, such that the projection of
$C(\mathcal{I}_{t})$ onto this subspace has an uncertainty angle less than
$\pi/2$. The high-level idea will be that, if the effective difference
$\delta_{t}^{\pi}$ at period $t$ is sufficiently close to the subspace
$\Delta_{t}$, then we can operate in that period by ignoring everything that
does not lie in the subspace $\Delta_{t}$. In such periods, we can operate in
a way that is similar to EllipsoidalCones. Meanwhile, if the effective
difference $\delta_{t}^{\pi}$ is far from $\Delta_{t}$, that means we will
gain enough information in period $t$ in the sense that the projection of
$C(\mathcal{I}_{t+1})$ will be pointed in a higher-dimensional subspace than
$\Delta_{t}$. That is, when the effective difference $\delta_{t}^{\pi}$ is far
from $\Delta_{t}$, we will make progress via a _subspace update_ from
$\Delta_{t}$ to $\Delta_{t+1}$. In what follows, we will show the
modifications needed to operate within subspaces, as well as show how to
perform the subspace updates.

We define the orthogonal projection of a vector $c$ onto the subspace $\Delta$
by $\Pi_{\Delta}(c)=\operatorname*{arg\,min}_{\hat{c}\in\Delta}\|c-\hat{c}\|.$
We will use the same notation $\Pi_{\Delta}(C)$ for the projection of a set
$C$. We will be working with ellipsoidal cones $E(W_{t},U_{t})$ that belong to
the subspaces $\Delta_{t}$ and contain the projections of the knowledge sets
$\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))$. If we collect an effective difference
sufficiently close to $\Delta_{t}$, meaning that
$\|\delta_{t}^{\pi}-\Pi_{\Delta_{t}}(\delta_{t}^{\pi})\|\leq\eta$ for a given
$\eta>0$ that we will choose, we say that we are in a _pointed period_. Just
as in Section 4, pointed periods can be subdivided into cone-update periods
and low-regret periods. For a period where
$\|\delta_{t}^{\pi}-\Pi_{\Delta_{t}}(\delta_{t}^{\pi})\|>\eta$, we call it a
_subspace-update period_ , and we perform a subspace update and define a new
ellipsoidal cone in $\Delta_{t+1}$ that contains
$\Pi_{\Delta_{t+1}}(C(\mathcal{I}_{t+1}))$. Our actions are still determined
according to the circumcenter policy.

Working with Subspaces. Before studying the mechanics of the pointed-case
algorithm within a subspace, we need to argue that there exists a positive-
dimensional subspace $\Delta_{t}$ where $\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))$
belongs to a pointed cone. This is not necessarily true for the initial
knowledge set $C_{0}$ (for example, if $C_{0}=S^{d}$, then the statement is
clearly untrue). The next lemma shows that this statement is true as soon as
the the decision-maker selects an action such that
$f_{t_{0}}(x_{{t_{0}}}^{\pi})\neq f_{{t_{0}}}(x^{\star}_{{t_{0}}})$.

######  Lemma 6 (Existence of subspace).

Let $t_{0}$ be the first period $t$ such that $f_{t}(x_{t}^{\pi})\neq
f_{t}(x^{\star}_{t})$ and let:

$\delta_{t_{0}}^{\pi}=\frac{f_{t_{0}}(x_{t_{0}}^{\pi})-f_{t_{0}}(x^{\star}_{t_{0}})}{\|f_{t_{0}}(x_{t_{0}}^{\pi})-f_{\tau}(x^{\star}_{t_{0}})\|},\quad\Delta_{t_{0}+1}=\\{c\in\mathbb{R}^{d}:\;c=\gamma\delta_{t_{0}}^{\pi},\;\gamma\in\mathbb{R}\\}.$

Then, $\Pi_{\Delta_{t_{0}+1}}\left(C(\mathcal{I}_{t_{0}+1}^{\pi})\right)$
lives in a pointed cone. Moreover, the regret is zero for every $t<t_{0}$.

Since we incur no regret before $f_{t_{0}}(x_{{t_{0}}}^{\pi})\neq
f_{{t_{0}}}(x^{\star}_{{t_{0}}})$, we will assume through the rest of the text
that $t_{0}=1$. For a given period $t\geq 2$, we can assume the dimension of
$\dim(\Delta_{t})=p\in\\{1,...,d\\}$. The dimension of the matrices $W_{t}$
and $U_{t}$ will be determined by the dimension of the subspace $\Delta_{t}$
since we are forcing the ellipsoidal cone $E(W_{t},U_{t})$ to live in
$\Delta_{t}$. Then, the matrix $U_{t}\in\mathbb{R}^{p}\times\mathbb{R}^{p}$ is
represented under some $\mathbb{R}^{p}$ basis for $\Delta_{t}$. We define the
matrix $B_{\Delta_{t}}\in\mathbb{R}^{p}\times\mathbb{R}^{d}$ to be a matrix
with $p$ rows built with orthonormal vectors that live in $\Delta_{t}$ (the
precise construction of $B_{\Delta_{t}}$ will be discussed later when we
define the steps for a subspace update). The matrix $B_{\Delta_{t}}$ will be
useful because it allows us to pick some vector in $c\in\Delta_{t}$
(represented under the canonical basis in $\mathbb{R}^{d}$), and write it
under a basis of $\Delta_{t}$. In order to do so, we can simply compute
$\bar{c}=B_{\Delta_{t}}c$. Then, $\bar{c}\in\mathbb{R}^{p}$ is a
representation of $c\in\Delta_{t}$ under the basis of $\Delta_{t}$.
Equivalently, to represent any $\bar{c}\in
E(W_{t},U_{t})\subset\mathbb{R}^{p}$ under the canonical basis in
$\mathbb{R}^{d}$, it suffices to compute $c=B_{\Delta_{t}}^{\prime}\bar{c}$.

As previously mentioned, the algorithm will classify the periods into three
categories: low-regret, cone-update and subspace-update periods. Let

$r_{t}^{\pi}=\delta_{t}^{\pi}-\Pi_{\Delta_{t}}(\delta_{t}^{\pi})$

denote the residual of the projection of the effective difference onto
$\Delta_{t}$. If the residual $r_{t}^{\pi}$ is small, in the sense that
$\|r_{t}^{\pi}\|\leq\eta$ for a given choice of $\eta>0$, then we will say
that we are in a pointed period. Pointed periods can be of two kinds: low-
regret and cone-update. Denote
$\bar{\delta}_{t}=U_{t}^{-1}B_{\Delta_{t}}^{\prime}\Pi_{\Delta_{t}}(\delta_{t}^{\pi})$.
The multiplication with the matrix $B_{\Delta_{t}}^{\prime}$ allows us to
write $\Pi_{\Delta_{t}}(\delta_{t}^{\pi})$ in a basis that is compatible with
$E(W_{t},U_{t})$. The second operation with the matrix $U^{-1}_{t}$ allows us
to work with ellipsoidal cones in standard-position. Analogously to Eq. (12),
we say a pointed period is a low-regret period if

$\displaystyle{\bar{\delta}_{t,[2:p]}}^{\prime}W_{t}{\bar{\delta}_{t,[2:p]}}\leq\epsilon^{2}.$
(13)

If the period is pointed but the equation above is violated, then we say
period $t$ is a cone-update period. When $\|r_{t}^{\pi}\|>\eta$, we are not in
a pointed period, but instead in a subspace-update period.

Low-Regret Periods. Low-regret periods are the simplest to analyze since the
knowledge superset is not updated on these periods. Our only task here is to
show that we have a certificate of low regret for the circumcenter policy in
such periods. The next lemma shows that if (i) the projection of the knowledge
set is contained in the ellipsoidal cone, (ii) the period is pointed, and
(iii) Eq. (13) is satisfied, then the circumcenter policy incurs low regret
that period. However, compared to Lemma 4, we do incur an additional regret of
$\eta$ since we are working with the projection of the effective difference
onto $\Delta_{t}$ instead of working with the effective difference directly.

######  Lemma 7 (Regret incurred in low-regret periods).

Assume that $\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))\subseteq E(W_{t},U_{t})$. If
$\|r_{t}^{\pi}\|\leq\eta$, and Eq. (13) is satisfied, then the regret in that
period is upper bounded by $\epsilon+\eta$.

Cone-Update Periods. There are two important differences in how we perform a
cone update in ProjectedCones versus in EllipsoidalCones. The first difference
is a simple one: we are working in a subspace $B_{\Delta_{t}}$ of dimension
$p$, rather than the original $d$-dimensional space. The second change is more
complex. When we perform a standard ellipsoid method update using a projected
effective difference, we run the risk of removing the true cost from our
knowledge set because the projected effective difference is not exactly the
same as the effective difference. To deal with this, we modify the ellipsoid
method to use what is called a shallow cut (Grötschel et al., 1993) instead of
what the traditional ellipsoid method uses, which is a center cut. A shallow
cut is a cut that doesn’t cut through the center of the ellipsoid and instead
leaves more than half of the original ellipsoid behind. The reason to use a
shallow cut is to create a buffer to ensure we do not remove the true cost.
The needed shallowness will be a function of our choice of $\eta$, as a larger
value of $\eta$ would imply that the true effective difference might be
further away from the projected effective difference, and therefore we’d need
a bigger buffer. Our implementation of ConeUpdate already allows for shallow
cuts via a margin $\eta$, and allows for us to operate in the $p$-dimensional
subspace $\Delta_{t}$.

The next lemma shows the reduction in the product of eigenvalues when we run
the robust version of a cone update. We call this cone update a robust one
since it includes a positive margin $\eta$. It assumes that we are working in
a dimension $p>1$ as the ellipsoidal cone is degenerate when $p=1$ (it’s a
ray) and, thus, cone-update periods do not occur when $p=1$.

######  Lemma 8 (Robust ellipsoidal cone updates).

Set $\eta=\epsilon/2d$ and suppose we run the algorithm _ConeUpdate_ with
inputs $W_{t},U_{t},\Pi_{\Delta_{t}}(\delta_{t}^{\pi}),\eta,$ $B_{\Delta_{t}}$
and $p\in\\{2,...,d\\}$. Assume that
$\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))\subseteq E(W_{t},U_{t})$. Then,
$\Pi_{\Delta_{t}}(C(\mathcal{I}_{t+1}))\subseteq
E(W_{t},U_{t})\cap\\{c\in\mathbb{R}^{d}\;{\delta_{t}^{\pi}}^{\prime}\Pi_{\Delta_{t}}(c)\geq
0\\}\subseteq E(W_{t+1},U_{t+1})$. Moreover,
$\prod_{i=1}^{p-1}\lambda_{i}(W_{t+1})\leq
e^{-1/20(p-1)}\prod_{i=1}^{p-1}\lambda_{i}(W_{t})$.

The next result leverages the reduction in the product of eigenvalues to bound
the number of times cone-update periods occur while we operate in a
$p$-dimensional subspace.

######  Lemma 9 (Cone-updates per dimension).

Let $p\in\\{2,...,d\\}$ and $I_{T}^{\pi,p}$ be the number of cone-updates
while $\dim(\Delta_{t})=p$ and let $t_{0}^{p}$ be the first period such that
$\dim(\Delta_{t})=p$. Suppose
$\lambda_{1}(W_{t_{0}^{p}})>\left(\frac{\epsilon}{10(d-1)}\right)^{2}$. Then,

$I_{T}^{\pi,p}\leq
20(p-1)^{2}\ln\left(\frac{10p\tan\alpha(E(W_{t_{0}^{p}},U_{t_{0}^{p}}))}{\epsilon}\right).$

If $\lambda_{1}(W_{t_{0}^{p}})\leq\left(\frac{\epsilon}{10(d-1)}\right)^{2}$,
then $I_{T}^{\pi,p}=0$ and the per period regret is bounded above by
$\epsilon+\eta$ while $\dim(\Delta_{t})=p$ .

Subspace Update. Next, focus on periods during which the effective difference
is “sufficiently orthogonal” from the subspaces. In such periods, the
decision-maker can increase the dimensionality of the subspace while ensuring
pointedness in a new subspace of higher dimension. We now show how the
subspaces are constructed. We initialize the first-period subspace with
$\Delta_{1}=\\{0\\}$. Once the decision-maker observes an effective difference
such that $\|r_{t}^{\pi}\|>\eta$ for some pre-specified $\eta$, this effective
difference is incorporated into the definition of the subspace $\Delta_{t+1}$.
That is, let $\tau(t)$ be the set of time periods such that
$\|r_{i}^{\pi}\|>\eta$, for $i\leq t$. Then, we define $\Delta_{t}$ to be the
subspace defined by the effective differences from periods in $\tau(t)$:
$\Delta_{t}=\left\\{c\in\mathbb{R}^{d}:\;c=\sum_{i\in\tau(t)}\gamma_{i}\delta^{\pi}_{i},\;\gamma_{i}\in\mathbb{R}\right\\}.$

The definition of $\Delta_{t}$ allows us to construct the matrix
$B_{\Delta_{t}}$. It suffices to take each row as the effective differences
$\delta_{i}^{\pi}$ and apply the Gram-Schmidt procedure in order to obtain
orthogonal rows with unit norm (see, for instance, Björck (1994), for
implementation details). Moreover, the subspace updating rule implies that
there are at most $d$ periods where we increase the dimensionality of our
space. Therefore, the cumulative regret incurred in subspace-update periods is
small (upper bounded by $d$). The key arguments we need to show are that
$\Pi_{\Delta_{t+1}}(C(\mathcal{I}_{t+1}))$ is pointed within $\Delta_{t+1}$,
and that the uncertainty angle of the new set is controlled by the parameter
$\eta$. In order to prove these points, we will consider a polyhedral cone
that contains the projection of the knowledge set onto that period’s subspace.
The period $t$ polyhedral cone is given by:

$K_{t}=\\{c\in\Delta_{t}:\;c^{\prime}\delta_{i}^{\pi}\geq 0,\;i\in\tau(t)\\}.$
(14)

We will next show that our projected knowledge set is contained within $K_{t}$
and that we can bound the uncertainty angle of $K_{t}$.

######  Lemma 10 (Uncertainty angle of polyhedral cone).

Let $\eta\in(0,1]$ and let $K_{t}$ be defined according to Eq. (14). Then, for
every period $t$, $\Pi_{\Delta_{t}}(C(\mathcal{I}_{t}))\subseteq K_{t}$. Also,
the circumcenter of $K_{t}$ can be computed in polynomial time from the inputs
$\delta_{i}^{\pi}$, with $i\in\tau(t)$. Furthermore, the uncertainty angle of
$K_{t}$ is bounded by
$\alpha(K_{t})\leq\arccos\left({\eta^{d-1}}/{d^{3/2}}\right).$

Lemma 10 ensures that every time we increase the dimension of our subspace, we
can construct an ellipsoidal cone in the new higher-dimensional space that has
a bounded uncertainty angle. If we perform a subspace update in period $t$,
then we will restart our ellipsoidal cone in period $t+1$ with a revolution
cone with aperture angle given by $\arccos({\eta^{d-1}}/{d^{3/2}})$ and axis
given by the circumcenter $\hat{c}(K_{t+1})$, which we compute using a
polynomial-time algorithm we call PolyCenter (see Algorithm 3).

The proof of Lemma 10 is based on various geometric ideas. We use duality to
show that providing an upper bound for the aperture angle of the smallest
revolution cone that contains $K_{t+1}$ is equivalent to provide a lower bound
for the aperture angle of the largest revolution cone contained in the dual of
$K_{t+1}$. We also show that in order to establish such property, it suffices
to quantify the “degree” of noncolinearity of the generators of the dual of
$K_{t+1}$. By using the fact that the dual cone of $K_{t+1}$ is generated
_only_ by the effective differences used for the subspace updates, we have by
the subspace updating rule that the effective differences are “sufficiently”
orthogonal to the subspace generated by the previous ones, the key of the
argument is to characterize the extent to which this holds for the overall
system.

input : effective differences $\delta_{i}$, $i\in\tau(t)$, basis $B$, new
dimension $p$.

$\bar{\delta}_{i}\leftarrow B\delta_{i}$, for all $i\in\tau(t)$;

$\tilde{z}\leftarrow\sum_{i\in\tau(t)}\bar{\delta}_{i}$;

$z\leftarrow\tilde{z}/\|\tilde{z}\|$;

for  _$1\leq k\leq p$_ do

Define $q_{k}=\chi_{k}/\|\chi\|_{2}$, where $\chi_{k}$ is the solution of the
linear system
$c^{\prime}z=1,\;{\bar{\delta}}_{i}^{\prime}c=0,\;i\in\tau(t),\;i\neq k$;

end for

Solve the optimization:
$\hat{c}\leftarrow\operatorname*{arg\,min}\|c\|^{2},\quad\mbox{s.t.
}\;c=\sum_{i=1}^{p}\gamma_{i}q_{i},\;\sum_{k=1}^{p}\gamma_{i}=1,\;\gamma_{k}\geq
0$;

output : $\hat{c}/\|\hat{c}\|$.

Algorithm 3 PolyCenter

Figure 5 illustrates the two types of updates. On the one hand, in Figure 5(a)
we have an effective difference $\delta_{t}^{\pi}$ close to the current
subspace $\Delta_{t}$, therefore, the vector $\delta_{t}^{\pi}$ is not
sufficiently informative for a subspace update. In this case, we can work with
the projection of $\delta_{t}^{\pi}$ in order to perform a cone update within
the subspace (Figure 5(b)). On the other hand, Figure 5(c) shows an effective
difference $\delta_{t}^{\pi}$ that gives sufficient information about the
third dimension of the problem. Therefore, we can include $\delta_{t}^{\pi}$
in $\tau(t)$ and fit a sufficiently pointed ellipsoidal cone in
$\mathbb{R}^{3}$ (Figure 5(d)).

(a)

(b)

(c)

(d)

Figure 5: Two types of cone updates. In $(a)$ and $(b)$, we peform a cone
update within the subspace $\Delta_{t}$. In $(c)$ and $(d)$ we have a subspace
update.

The Algorithm for the General Case. We have now presented all of the different
parts of our main algorithm, ProjectedCones, including how to verify the kind
of period we are in (low-regret, cone-update or subspace-update) and what
update to perform in cone-update and subspace-update periods. The full
specification of ProjectedCones is presented in Algorithm 4.

input : $T,\eta,\epsilon$

Set $c_{1}^{\pi}=e_{1}$ and $x^{\pi}_{1}\in\psi(c^{\pi}_{1},{\cal
X}_{1},f_{1})$;

Observe feedback $x^{\star}_{1}$ and set
$\delta^{\pi}_{1}=\frac{f_{1}(x^{\pi}_{1})-f_{1}(x^{\star}_{1})}{\|f_{1}(x^{\pi}_{1})-f_{1}(x^{\star}_{1})\|}$;

$\tau(t)\leftarrow 1$,
$\Delta_{2}\leftarrow\left\\{c\in\mathbb{R}^{d}:\;c=\gamma\delta_{1}^{\pi},\;\gamma\in\mathbb{R}\right\\}$,
$p=1$;

Set $W_{2}\leftarrow 0$ and $U_{2}\subset\Delta_{2}$ with first column
$\delta_{1}^{\pi}$;

for  _$2\leq t\leq T$_ do

Set $c_{t}^{\pi}\leftarrow B_{\Delta_{t}}^{\prime}U_{t}e_{1}$ and
$x^{\pi}_{t}\in\psi(c^{\pi}_{t},{\cal X}_{t},f_{t})$;

Observe feedback $x^{\star}_{t}$;

Set
$\delta_{t}^{\pi}=\frac{f_{t}(x^{\pi}_{t})-f_{t}(x^{\star}_{t})}{\|f_{t}(x^{\pi}_{t})-f_{t}(x^{\star}_{t})\|}$
and $r^{\pi}_{t}=\delta^{\pi}_{t}-\Pi_{\Delta_{t}}(\delta^{\pi}_{t})$;

if  _$\|r_{t}^{\pi}\|\leq\eta$_ then

Set
$\delta=U_{t}^{-1}B_{\Delta_{t}}\Pi_{\Delta_{t}}(\delta^{\pi}_{t},p)\in\mathbb{R}^{p}$;

if  _${(\delta)}^{\prime}_{[2:p]}W_{t}{(\delta)}_{[2:p]}\leq\epsilon^{2}$_
then

$W_{t+1},U_{t+1},\Delta_{t+1}\leftarrow W_{t},U_{t},\Delta_{t}$ ;

else

$W_{t+1},U_{t+1}\leftarrow\mbox{{ConeUpdate}}(\Pi_{\Delta_{t}}(\delta_{t}^{\pi}),W_{t},U_{t},\eta,B_{\Delta_{t}},p)$;

$\Delta_{t+1}\leftarrow\Delta_{t}$;

end if

else

$\tau(t+1)\leftarrow(t,\tau(t)),\;p\leftarrow p+1$;

$\Delta^{\pi}_{t+1}\leftarrow\left\\{c\in\mathbb{R}^{d}:\;c=\sum_{i\in\tau(t)}\gamma_{i}\delta^{\pi}_{i},\;\gamma_{i}\in\mathbb{R}\right\\}$;

Construct $B_{\Delta_{t+1}}$ orthonormal with the linearly independent vectors
$\delta_{i}^{\pi},\;i\in\tau(t+1)$;

$u_{1}\leftarrow\texttt{PolyCenter}(\delta_{i}^{\pi},\;i\in\tau(t+1),B_{\Delta_{t+1}},p)$;

Set $W_{t+1}\leftarrow\frac{d^{3}}{\eta^{2(d-1)}}I_{p-1}$ and
$U_{t+1}\subset\Delta_{t+1}$ with first column $u_{1}$;

end if

end for

Algorithm 4 ProjectedCones

Our main result shows that this algorithm is computationally efficient and
incurs regret that is logarithmic in $T$, independently of the nature of the
initial knowledge set.

######  Theorem 4 (Regret for general case).

Set $\epsilon=d/T$ and $\eta=\epsilon/2d$ in _ProjectedCones_. Consider any
weakly geodesically convex set $C_{0}\subseteq S^{d}$. The worst-case regret
of the _ProjectedCones_ policy $\pi$ is upper bounded as follows.

${\cal WCR}^{\pi}_{T}\left(C_{0}\right)\leq\mathcal{O}\left(d^{4}\ln
T\right).$

Moreover, this algorithm runs in polynomial time in $d$ and $T$.

In Theorem 3, we had already established the possibility of obtaining
logarithmic dependence for this class of problems, but this dependence relied
on the nature of initial knowledge set. With Theorem 4 above, we have now
established that the possibility of achieving logarithmic dependence on the
time horizon is universal: it is independent of the nature of the initial
knowledge set. As discussed in the introduction, the best known regret bounds
to date were $\mathcal{O}(\sqrt{T})$ for linear context functions, as
developed in Bärmann et al. (2017). These were based on leveraging online
learning algorithms such as online gradient descent and exponential weights
updates in order to learn the objective function solved by the expert. Theorem
4 establishes that it is possible to achieve logarithmic regret by leveraging
the geometry of the problem at hand and tailoring the algorithms given the
geometry and the nature of the feedback at hand.

For our algorithm, the structure of the knowledge set determines the
dependence on $d$. The term $d^{4}$ follows from us running a variation of
EllipsoidalCones $d$ times, essentially restarting whenever we perform a
subspace update, and the regret of that algorithm being
$\mathcal{O}(d^{2}\ln(T\tan\alpha(K))$ for an initial set $K$. The final $d$
factor emerges from using Lemma 10 to bound $\tan\alpha(K)$.

#### Remark on the nature of the bound.

Our algorithm ProjectedCones enjoys an important additional feature. While
implicit in our analysis, the bound on the worst-case case regret in Theorem 4
can be interpreted as the “loss per unit of cost.” That is, if
$\|c^{\star}\|\neq 1$, the bound on the worst-case case regret can be shown to
be proportional to $\|c^{\star}\|$. Note that in general, the worst-case
regret is driven by both the norm of $c^{\star}$ as well as the quality of the
decisions. It might be possible to construct alternative algorithms with good
regret bounds where, if $\|c^{\star}\|$ is small, the regret is driven by the
small norm rather than good decisions. We do not take this route: our
algorithm produces high-quality decisions even when $\|c^{\star}\|$ is small.
The way we achieve this is by working with the normalized cost and creating
cone-shaped objects that contain the knowledge sets. In this sense, we obtain
a stronger notion of performance: we obtain low regret in the natural unit of
analysis, which is the cost vector norm.

##  6 Conclusion and further directions

In the offline setting, we have shown that without any particular assumption
about the offline data $\mathcal{D}$, the circumcenter policy achieves the
minimax regret. Furthermore, the regret of the circumcenter policy is
instance-dependent and fully characterized by the uncertainty angle of the set
of consistent cost vectors implied by the offline data. We also demonstrated
that the online setting presents a new set of challenges. Indeed, we show that
being myopic leads to a linear regret with respect to the time horizon and
significant care should be taken to construct dynamic robust and informative
policies. The key to ensure learning is to force what we defined as inverse
exploration, where nature is induced to choose between “exploring for us” or
causing no regret. We have shown that such inverse exploration can be
conducted effectively by regularizing the knowledge sets over time, leading to
the first logarithmic regret results for this class of problems.

The present paper opens many avenues for future research. A first interesting
avenue is to explore if the dimensionality dependence on the regret can be
improved. Another complementary question is to develop impossibility results
for this class of problems. Finally, a natural extension of the current
framework would be to allow for the possibility of noisy feedback. It would be
interesting to explore whether ideas developed for contextual search in
Krishnamurthy et al. (2020) to handle irrational agents could be used in the
present context.

## References

  * Abbeel and Ng (2004) P. Abbeel and A. Y. Ng.  Apprenticeship learning via inverse reinforcement learning.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 1, 2004.
  * Ahuja and Orlin (2001) R. K. Ahuja and J. B. Orlin.  Inverse optimization.  _Operations Research_ , 49(5):771–783, 2001.
  * Amin et al. (2015) K. Amin, R. Cummings, L. Dworkin, M. Kearns, and A. Roth.  Online learning and profit maximization from revealed preferences.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 29, 2015.
  * Amin et al. (2017) K. Amin, N. Jiang, and S. Singh.  Repeated inverse reinforcement learning.  _arXiv preprint arXiv:1705.05427_ , 2017.
  * Arora and Doshi (2021) S. Arora and P. Doshi.  A survey of inverse reinforcement learning: Challenges, methods and progress.  _Artificial Intelligence_ , page 103500, 2021.
  * Aswani et al. (2018) A. Aswani, Z.-J. Shen, and A. Siddiq.  Inverse optimization with noisy data.  _Operations Research_ , 66(3):870–892, 2018.
  * Balcan et al. (2014) M.-F. Balcan, A. Daniely, R. Mehta, R. Urner, and V. V. Vazirani.  Learning economic parameters from revealed preferences.  In _International Conference on Web and Internet Economics_ , pages 338–353. Springer, 2014.
  * Bärmann et al. (2017) A. Bärmann, S. Pokutta, and O. Schneider.  Emulating the expert: inverse optimization through online learning.  In _Proceedings of the 34th International Conference on Machine Learning_ , pages 400–410, 2017.
  * Bastani et al. (2021) H. Bastani, O. Bastani, and W. P. Sinchaisri.  Learning best practices: Can machine learning improve human decision-making?  _Working paper, University of Pennsylvania_ , 2021.
  * Beigman and Vohra (2006) E. Beigman and R. Vohra.  Learning from revealed preference.  In _Proceedings of the 7th ACM Conference on Electronic Commerce_ , pages 36–42, 2006.
  * Bertsimas et al. (2015) D. Bertsimas, V. Gupta, and I. C. Paschalidis.  Data-driven estimation in equilibrium using inverse optimization.  _Mathematical Programming_ , 153(2):595–633, 2015\.
  * Björck (1994) Å. Björck.  Numerics of gram-schmidt orthogonalization.  _Linear Algebra and Its Applications_ , 197:297–316, 1994\.
  * Boyd and Vandenberghe (2004) S. Boyd and L. Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Chan et al. (2019) T. C. Chan, T. Lee, and D. Terekhov.  Inverse optimization: Closed-form solutions, geometry, and goodness of fit.  _Management Science_ , 65(3):1115–1135, 2019\.
  * Chen et al. (2021) N. Chen, A. Cire, M. Hu, and S. Lagzi.  Model-free assortment pricing with transaction data.  _arXiv preprint arXiv:2101.02251_ , 2021.
  * Cohen et al. (2020) M. Cohen, I. Lobel, and R. Paes Leme.  Feature-based dynamic pricing.  _Management Science_ , 66(11):4921–4943, 2020\.
  * Dong et al. (2018) C. Dong, Y. Chen, and B. Zeng.  Generalized inverse optimization through online learning.  In _Advances in Neural Information Processing Systems_ , pages 86–95, 2018.
  * Esfahani et al. (2018) P. M. Esfahani, S. Shafieezadeh-Abadeh, G. A. Hanasusanto, and D. Kuhn.  Data-driven inverse optimization with imperfect information.  _Mathematical Programming_ , 167(1):191–234, 2018\.
  * Feng et al. (2018) Y. Feng, R. Caldentey, and C. T. Ryan.  Learning customer preferences from personalized assortments.  _Available at SSRN_ , 2018.
  * Grötschel et al. (1993) M. Grötschel, L. Lovász, and A. Schrijver.  The ellipsoid method.  In _Geometric Algorithms and Combinatorial Optimization_ , pages 64–101. Springer, 1993.
  * Henrion and Seeger (2010) R. Henrion and A. Seeger.  Inradius and circumradius of various convex cones arising in applications.  _Set-Valued and Variational Analysis_ , 18(3-4):483–511, 2010.
  * Hwang (2004) S.-G. Hwang.  Cauchy’s interlace theorem for eigenvalues of hermitian matrices.  _The American Mathematical Monthly_ , 111(2):157–159, 2004.
  * Jabbari et al. (2016) S. Jabbari, R. M. Rogers, A. Roth, and S. Z. Wu.  Learning from rational behavior: Predicting solutions to unknown linear programs.  _Advances in Neural Information Processing Systems_ , 29:1570–1578, 2016.
  * Keshavarz et al. (2011) A. Keshavarz, Y. Wang, and S. Boyd.  Imputing a convex objective function.  In _2011 IEEE International Symposium on Intelligent Control_ , pages 613–619. IEEE, 2011.
  * Khachiyan (1979) L. G. Khachiyan.  A polynomial algorithm in linear programming.  _Doklady Akademii Nauk_ , 244(5):1093–1096, 1979\.
  * Krishnamurthy et al. (2020) A. Krishnamurthy, T. Lykouris, C. Podimata, and R. Schapire.  Contextual search in the presence of irrational agents.  _arXiv preprint arXiv:2002.11650_ , 2020.
  * Liu et al. (2021) A. Liu, R. Paes Leme, and J. Schneider.  Optimal contextual pricing and extensions.  In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 1059–1078. SIAM, 2021.
  * Lobel et al. (2018) I. Lobel, R. Paes Leme, and A. Vladu.  Multidimensional binary search for contextual decision-making.  _Operations Research_ , 66(5):1346–1361, 2018\.
  * Lovell (2008) M. C. Lovell.  A simple proof of the fwl (frisch-waugh-lovell) theorem.  _The Journal of Economic Education_ , 39(1):88–91, 2008.
  * Nowozin and Lampert (2011) S. Nowozin and C. H. Lampert.  _Structured learning and prediction in computer vision_ , volume 6.  Now publishers Inc, 2011.
  * Osa et al. (2018) T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, and J. Peters.  An algorithmic perspective on imitation learning.  _arXiv preprint arXiv:1811.06711_ , 2018.
  * Osokin et al. (2017) A. Osokin, F. Bach, and S. Lacoste-Julien.  On structured prediction theory with calibrated convex surrogate losses.  _arXiv preprint arXiv:1703.02403_ , 2017.
  * Paes Leme and Schneider (2018) R. Paes Leme and J. Schneider.  Contextual search via intrinsic volumes.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 268–282. IEEE, 2018.
  * Ratliff et al. (2006) N. D. Ratliff, J. A. Bagnell, and M. A. Zinkevich.  Maximum margin planning.  In _Proceedings of the 23rd international conference on Machine learning_ , pages 729–736, 2006.
  * Raveh (1985) A. Raveh.  On the use of the inverse of the correlation matrix in multivariate data analysis.  _The American Statistician_ , 39(1):39–42, 1985\.
  * Roth et al. (2016) A. Roth, J. Ullman, and Z. S. Wu.  Watch and learn: Optimizing from revealed preferences feedback.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 949–962, 2016.
  * Sauré and Vielma (2019) D. Sauré and J. P. Vielma.  Ellipsoidal methods for adaptive choice-based conjoint analysis.  _Operations Research_ , 67(2):315–338, 2019.
  * Seeger and Vidal-Nuñez (2017) A. Seeger and J. Vidal-Nuñez.  Measuring centrality and dispersion in directional datasets: the ellipsoidal cone covering approach.  _Journal of Global Optimization_ , 68(2):279–306, 2017.
  * Sutton and McCallum (2006) C. Sutton and A. McCallum.  An introduction to conditional random fields for relational learning.  _Introduction to statistical relational learning_ , 2:93–128, 2006.
  * Taskar et al. (2005) B. Taskar, V. Chatalbashev, D. Koller, and C. Guestrin.  Learning structured prediction models: A large margin approach.  In _Proceedings of the 22nd International Conference on Machine Learning_ , pages 896–903, 2005.
  * Thai and Bayen (2018) J. Thai and A. M. Bayen.  Imputing a variational inequality function or a convex objective function: A robust approach.  _Journal of Mathematical Analysis and Applications_ , 457(2):1675–1695, 2018.
  * Toubia et al. (2007) O. Toubia, J. Hauser, and R. Garcia.  Probabilistic polyhedral methods for adaptive choice-based conjoint analysis: Theory and application.  _Marketing Science_ , 26(5):596–610, 2007.  doi: 10.1287/mksc.1060.0257.
  * Ward et al. (2019) A. Ward, N. Master, and N. Bambos.  Learning to emulate an expert projective cone scheduler.  In _2019 American Control Conference (ACC)_ , pages 292–297. IEEE, 2019.
  * Zadimoghaddam and Roth (2012) M. Zadimoghaddam and A. Roth.  Efficiently learning from revealed preference.  In _International Workshop on Internet and Network Economics_ , pages 114–127. Springer, 2012.
  * Ziebart et al. (2008) B. D. Ziebart, A. L. Maas, J. A. Bagnell, and A. K. Dey.  Maximum entropy inverse reinforcement learning.  In _Proceedings of AAAI_ , volume 8, pages 1433–1438. Chicago, IL, USA, 2008.

Electronic Companion: Appendix for
Contextual Inverse Optimization: Offline and Online Learning
Omar Besbes666Columbia Business School —<EMAIL_ADDRESS>Yuri
Fonseca777Columbia Business School —<EMAIL_ADDRESS>and Ilan
Lobel888NYU Stern School of Business —<EMAIL_ADDRESS>
##  Appendix A Examples of problem classes that fall under our formulation

Next, to illustrate the framework introduced in Section 2, we provide a few
prototypical classes of problems that fall under it and relate these more
precisely to some existing papers discussed in Section 1.2.

A first special case is one in which the decision-maker faces a sequence of
optimization problems of the form
$\min_{x\in\mathcal{X}_{t}}x^{\prime}c^{\star}$. This formulation was studied
in Bärmann et al. (2017). A natural extension of this problem, also studied in
Bärmann et al. (2017), is to consider linear context functions $f_{t}$. In
this case, the sequence of optimization problems becomes solving
$\min_{x\in\mathcal{X}_{t}}x^{\prime}Z_{t}c^{\star}$ for the context function
$f_{t}(x)=x^{\prime}Z_{t}$.

As a concrete application of the above, consider a problem where the goal is
to learn preferences from observing consumers’ behavior. At each time $t$, the
consumer faces an arbitrary bundle $S_{t}$ of $J_{t}$ products, each with
features $z_{t}^{j}\in\mathbb{R}^{d}$ and price $p_{t}^{j}$. The consumer
chooses products in the assortment in order to maximize his/her utility
function subject to a budget constraint of $b_{t}$. Let
$Z_{t}\in\mathbb{R}^{J_{t}}\times\mathbb{R}^{d}$ be the matrix where each row
$j$ is given by the vector of features of the product $j$, i.e., $z_{t}^{j}$.
Let also $p_{t}=(p_{t}^{1},...,p_{t}^{J_{t}})$ be the vector of prices of
products $j=1,...,J_{t}$ available at time $t$. At each time, the consumer
solves

$x^{\star}_{t}=\operatorname*{arg\,min}_{x\in\mathcal{X}_{t}}f_{t}(x)^{\prime}c^{\star},\quad\mbox{
where }{\cal X}_{t}=\\{x\in\\{0,1\\}^{J_{t}}\;:\;x^{\prime}p_{t}\leq
b_{t}\\},\;f_{t}(x)=-x^{\prime}Z_{t},$

which is a sequence of adversarial knapsack problems where the universe of
products, the budget constraint and the prices are allowed to change and are
arbitrarily selected (by nature). This relates to the formulation explored in
the learning from revealed preferences literature.

When there is no budget and $|S_{t}|=1$, the problem becomes one of sequential
customer buy/no buy decisions. The question then is how to leverage such
binary feedback. The consumer is rational and buys the product if and only if
the utility of buying it, modeled as ($z_{t}^{\prime}\theta$) satisfies
$z_{t}^{\prime}\theta\geq p_{t}$. Here the vector $\theta$ is unknown. The
consumer contextual optimization problem is given by
$x^{\star}=\operatorname*{arg\,max}_{x\in\\{0,1\\}}(z_{t}^{\prime}\theta-
p_{t})x$. In our notation, this would correspond to context function
$f_{t}(x)=-x(z_{t},p_{t})$, feasible sets $\mathcal{X}=\\{0,1\\}$ and cost
vector $c^{\star}=(\theta,-1).$ Even though the structure of the feedback and
the contextual optimization problem faced by the consumer would be the same as
in the contextual pricing literature (see, e.g., Cohen et al. (2020)), the
problem described above is of different nature since the decision-maker is not
allowed to select the price of the product and can’t affect the feedback
directly. Here, the decision-maker’s action is a passive one, where instead of
setting the price, the decision-maker merely “guesses” if the product would be
bought or not by the consumer. This endows the decision-maker with
significantly less control on the information collected.

The flexibility of our contextual optimization formulation allows to encompass
works in imitation learning problems. In Ward et al. (2019), the authors
consider an online problem where the goal is to be able to mimic the optimal
scheduling policy of an expert for the following dynamic problem. At each time
$t$, the length (states) of $n$ queues $z_{t}\in\mathbb{R}^{n}$ is observed
and the expert solves
$x^{\star}_{t}=\operatorname*{arg\,max}_{x\in\mathcal{X}}x^{\prime}Bz_{t}$,
where $\mathcal{X}$ is the set of admissible schedule configurations that is
assumed to be bounded. The matrix $B$ is unknown to the decision-maker. This
problem falls under our formulation by defining $f_{t}$ to be the Kronecker
product between $x$ and $z_{t}$, $f_{t}(x)=x\otimes
z_{t}=(x_{[1]}z_{t},x_{[2]}z_{t},\cdots,x_{[n]}z_{t})$, and letting
$\mbox{vec}(B)$ be the operator that stacks the columns of $B$. We then have
that at each time $t$ the expert solves

$x^{\star}_{t}=\operatorname*{arg\,min}_{x\in\mathcal{X}}f_{t}(x)^{\prime}c^{\star},\quad\mbox{
where }f_{t}(x)=x\otimes z_{t},\mbox{ and }c^{\star}=-\mbox{vec}(B).$

Next, we illustrate that the framework also captures versions of problems in
inverse reinforcement learning. A version of the problem studied in Ratliff et
al. (2006) can be described as follows. At each period $t$, the decision-maker
faces a new Markov decision process (MDP) and the objective is to match the
state-action frequency of the expert. The initial state distribution and the
transition probabilities for the period $t$ MDP are known. We let the set of
feasible actions for the decision-maker $\mathcal{X}_{t}$ to be the set of
feasible state-action pair frequencies for the MDP. At the end of the period
(after a full run of the period $t$ MDP), the decision-maker observes the
optimal state-action pair frequency for that period’s MDP. At period $t$, let
$\mathcal{S}_{t}$ and $\mathcal{A}_{t}$ denote the spaces for state and
action, respectively. For each state-action pair
$(s,a)\in\mathcal{S}_{t}\times\mathcal{A}_{t}$, we have an associated
$d$-dimensional vector of features $\phi_{t}(s,a)$. We assume that the cost
function $r(s,a)$ associated with taking action $a$ in state $s$ is a linear
with respect to the vector of features, i.e.,
$r(s,a)=\phi_{t}(s,a)^{\prime}c^{\star}$. We also denote
$r\in\mathbb{R}^{|\mathcal{S}_{t}|\times\mathcal{A}_{t}}$ to be the cost
vector for each state-action pair. Let
$\Phi_{t}\in\mathbb{R}^{|\mathcal{S}_{t}|\times\mathcal{A}_{t}}\times\mathbb{R}^{d}$
be the matrix where each row is the feature vector associated with each of the
state-action pairs. Using the dual of the LP formulation for the MDP (cf.
Sutton and McCallum (2006)), we have that
$V_{\pi}=x_{\pi}^{\prime}r=x_{\pi}^{\prime}\Phi_{t}c^{\star}$, where $x_{\pi}$
is the vector of state-action pair frequency implied by policy $\pi$.
Therefore, at each time $t$ we would like to solve

$x^{\star}_{t}=\operatorname*{arg\,min}_{x\in\mathcal{X}_{t}}f_{t}(x)^{\prime}c^{\star},\quad\mbox{
where }f_{t}(x)=x^{\prime}\Phi_{t}.$

Finally, recall that a structured prediction problem is one where we observe
some input and we would like to predict a multidimensional output. Let the
inputs be denoted by $z\in\mathcal{Z}$, the outputs by $x\in\mathcal{X}(z)$
and the score function by $g(z,x)$. Our problem formulation includes special
cases of this class of problems with a regret objective; when it is possible
to assume a parametric form for $g(x,z)=-f(x,z)^{\prime}{c^{\star}}$ for a
known $f(x,z)$, then the forward problem is given by
$x^{\star}=\operatorname*{arg\,min}_{x\in\mathcal{X}(z)}f(x,z)^{\prime}c^{\star}$
for an unknown $c^{\star}$. Applications of structured predictions include,
e.g., natural language processing and image recognition (Taskar et al., 2005).

The examples above illustrate the generality of the formulation that we study,
but also that there is a potential to lift up some existing formulations
within a general framework of contextual inverse optimization with regret
objective.

##  Appendix B Appendix: Proofs

###### Proof of Lemma 1.

We first consider the cases where $\theta(c^{\star},c^{\pi})\geq\pi/2$. In
this case, nature can choose $f$ as the identity function and a set ${\cal
X}=\\{x_{1},x_{2}\\}$ such that $x_{2}-x_{1}=c^{\star}$. Note that
$(x_{2}-x_{1})^{\prime}c^{\star}=\|c^{\star}\|^{2}=1\geq 0$, and therefore
$x_{2}^{\prime}c^{\star}\geq x_{1}^{\prime}c^{\star}$, implying that
$x_{1}\in\psi(c^{\star},{\cal X},f)$. We also have that
$(x_{2}-x_{1})^{\prime}c^{\pi}={c^{\star}}^{\prime}c^{\pi}\leq 0$, where the
inequality follows from $\theta(c^{\star},c^{\pi})\geq\pi/2$. Thus,
$x_{1}^{\prime}c^{\pi}\geq x_{2}^{\prime}c^{\pi}$, implying that
$x_{2}\in\psi(c^{\pi},{\cal X},f)$. Therefore,
$\mathcal{L}(c^{\pi},c^{\star})\geq(x_{2}-x_{1})^{\prime}c^{\star}=\|c^{\star}\|^{2}=1$.

We now turn our attention to the case where
$0\leq\theta(c^{\star},c^{\pi})<\pi/2$. The proof is organized as follows. We
first introduce a relaxation of the maximization problem in the definition of
$\mathcal{L}$ (see Eq. (8)). Second, we show that the relaxation leads to a
semi-definite programming (SDP) formulation based on the realizability of Gram
matrices. Third, we derive an upper bound for the relaxed problem. The final
step is to construct an instance that attains this upper bound.

Step 1. Recall from Eq. (8) that
$\mathcal{L}(c^{\pi},c^{\star})=\sup_{\mathcal{X}\in\mathcal{B},\;f\in\mathcal{F},{x}^{\pi}\in\psi(c^{\pi},{\cal
X},f)}~{}\Bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}.$ For any
${\cal X}\in\mathcal{B}$, $f\in\mathcal{F}$, $c^{\star},c^{\pi}\in S^{d}$,
$x^{\star}\in\psi(c^{\star},{\cal X},f)$, and $x^{\pi}\in\psi(c^{\pi},{\cal
X},f)$, we have, by the optimality of $x^{\star}$ and $x^{\pi}$ (for their
respective problems), that $(f(x^{\pi})-f(x^{\star}))^{\prime}c^{\star}\geq 0$
and $(f(x^{\pi})-f(x^{\star}))^{\prime}c^{\pi}\leq 0$.

In particular, we have the following

$\displaystyle\mathcal{L}(c^{\pi},c^{\star})$ $\displaystyle=$
$\displaystyle\sup\left\\{\>(f(x^{\pi})-f(x^{\star}))^{\prime}c^{\star}\>:\>\mathcal{X}\in\mathcal{B},\;f\in\mathcal{F},x^{\pi}\in\psi(c^{\pi},{\cal
X},f),~{}x^{\star}\in\psi(c^{\star},{\cal X},f)\right\\}$ $\displaystyle\leq$
$\displaystyle\sup\left\\{\>\delta^{\prime}c^{\star}\>:\>\delta\in\mathbb{R}^{d},~{}\|\delta\|\leq
1,~{}\delta^{\prime}c^{\pi}\leq 0\right\\}$ $\displaystyle=$
$\displaystyle\sup\left\\{\>\delta^{\prime}c^{\star}\>:\>\delta\in\mathbb{R}^{d},~{}\|\delta\|=1,~{}\delta^{\prime}c^{\pi}\leq
0\right\\},$

where the inequality follows from noting that for any feasible $x^{\star}$,
$x^{\pi}$, if one sets $\delta=f(x^{\star})-f(x^{\pi})$, we must have that
$\|\delta\|\leq\|x^{\star}-x^{\pi}\|\leq 1$, and $\delta^{\prime}c^{\pi}\leq
0$. The last equality follows from the fact that an optimal solution will
always have a vector $\delta$ with maximal norm. Note that the set of
$\delta\in\mathbb{R}^{d}$ such that $\|\delta\|=1$ is the set $S^{d}$. We
therefore switch our attention to the optimization problem

$\displaystyle\sup\left\\{\>\delta^{\prime}c^{\star}\>:\>\delta\in{S}^{d},~{}\delta^{\prime}c^{\pi}\leq
0\right\\},$ (B-1)

which is an upper bound on the value of $\mathcal{L}(c^{\pi},c^{\star})$.

Step 2. We now analyze problem (B-1). In particular, we show how it can be
written as an SDP and solved explicitly. For any $c^{\star}$, $c^{\pi}$ and
$\delta\in S^{d}$, let us define the following matrices

$A=\begin{bmatrix}\delta&c^{\star}&c^{\pi}\end{bmatrix},\quad\mbox{and}\quad
B=A^{\prime}A.$

Then, $B$ is equal to

$B=\begin{bmatrix}1&\delta^{\prime}c^{\star}&\delta^{\prime}c^{\pi}\\\
\delta^{\prime}c^{\star}&1&c^{\prime}c^{\pi}\\\
\delta^{\prime}c^{\pi}&{c^{\star}}^{\prime}c^{\pi}&1\end{bmatrix}.$

Note that $B$ is the Gram matrix associated with the matrix $A$. Therefore, it
must belong to the set of symmetric positive semi-definite matrices (see
Chapter 8.3.1 of Boyd and Vandenberghe (2004)). Moreover, Cauchy-Schwartz
implies that all its entries are in $[-1,1]$. We also have that for any
feasible solution of Problem (B-1), the entry
$B_{1,3}=\delta^{\prime}c^{\pi}\leq 0$ and thus $B_{1,3}\in[-1,0]$.

Let $\mathcal{S}^{3}_{+}$ denote the set of symmetric positive semi-definite
matrices in $\mathbb{R}^{3\times 3}$ and let $\mathcal{M}^{3}$ denote the set
of symmetric matrices in $\mathbb{R}^{3\times 3}$. In turn, we have the
following relaxation:

$\displaystyle\sup\left\\{\>\delta^{\prime}c^{\star}~{}:~{}\delta\in{S}^{d},\delta^{\prime}c^{\pi}\leq
0\right\\}$ (B-2) $\displaystyle\leq$
$\displaystyle\sup\left\\{B_{1,2}\>:\>B\in\mathcal{S}^{3}_{+},\quad
B_{1,2}\in[-1,1],\quad B_{1,3}\in[-1,0],\quad
B_{2,3}={c^{\star}}^{\prime}c^{\pi}\right\\}$ $\displaystyle\leq$
$\displaystyle\sup\\{B_{1,2}\>:\>B\in\mathcal{M}^{3},\quad\det(B)\geq 0,\quad
B_{1,2}\in[-1,1],$ $\displaystyle\qquad\qquad\qquad B_{1,3}\in[-1,0],\quad
B_{2,3}={c^{\star}}^{\prime}c^{\pi}\\}$ $\displaystyle=$
$\displaystyle\sup\\{B_{1,2}\>:\>B\in\mathcal{M}^{3},\quad
1+2B_{1,2}B_{1,3}B_{2,3}-B_{1,2}^{2}-B_{1,3}^{2}-B_{2,3}^{2}\geq 0,$
$\displaystyle\qquad\qquad\quad B_{1,2}\in[-1,1],\quad B_{1,3}\in[-1,0],\quad
B_{2,3}={c^{\star}}^{\prime}c^{\pi}\\}$ $\displaystyle=$
$\displaystyle\sup\\{r\>:\>1+2\rho zr-z^{2}-\rho^{2}-r^{2}\geq 0,$
$\displaystyle\qquad\qquad\qquad-1\leq\rho\leq 0,\quad-1\leq r\leq 1,\quad
z={c^{\star}}^{\prime}c^{\pi}\\},$

where the last inequality follows from the relaxation to symmetric matrices
with non-negative determinants. To simplify notation, we denoted
$r=\delta^{\prime}c^{\star},\rho=\delta^{\prime}c^{\pi}$ and
$z={c^{\star}}^{\prime}c^{\pi}$.

Step 3. In the final step we upper bound the problem in Eq. (B-2). Let
$h(r)=1+2\rho zr-z^{2}-\rho^{2}-r^{2}$ and note that $h$ is a quadratic
function for any $\rho,z$. Also, $h$ is concave and admits two roots

$\displaystyle r_{+}$ $\displaystyle=$ $\displaystyle
z\rho+\sqrt{z^{2}\rho^{2}+(1-z^{2}-\rho^{2})},$ $\displaystyle r_{-}$
$\displaystyle=$ $\displaystyle
z\rho-\sqrt{z^{2}\rho^{2}+(1-z^{2}-\rho^{2})},$

such that $h(r)\geq 0$ if and only if $r\in[r_{-},r_{+}]$. Hence, for any
feasible $\rho,z$, the maximal achievable value of $r$ is $r_{+}$. Solving the
problem in Eq. (B-2) reduces to finding the feasible values of $\rho$ and $z$
that maximize $r_{+}$. When $\theta(c^{\star},c_{t}^{\pi})=0$, $z=1$, and
$r_{+}=0$, so there is no regret. Now we consider the case where
$0<\theta(c^{\star},c_{t}^{\pi})<\pi/2$. Note that $r_{+}$ is differentiable
with respect to $\rho$ and its derivative is given by

$\frac{\partial
r_{+}}{\partial\rho}=z+2\rho(z^{2}-1)\frac{1}{2\sqrt{z^{2}\rho^{2}+(1-z^{2}-\rho^{2})}}.$

Since $0<\theta(c^{\star},c^{\pi})$ implies $z<1$, the term inside the square
root is always greater than zero and the derivative is always well-defined on
the feasible set. Moreover, since $\theta(c^{\star},c^{\pi})<\pi/2$ implies
$z>0$ and $\rho\leq 0$ implies $\rho(z^{2}-1)\geq 0$, we get that the
derivative is non-negative on the feasible set. Hence, independently of the
value of $z$, the value of $r_{+}$ is maximized on the feasible set when
$\rho$ achieves its maximum value, $0$.

Note that for all $\rho\leq 0$, we have $r_{+}\leq\sqrt{1-z^{2}},$ with
equality when $\rho=0$. Recall that $z={c^{\star}}^{\prime}c^{\pi}$. Using the
identity $\sin^{2}x+\cos^{2}x=1$, we obtain
$r_{+}\leq\sqrt{1-({c^{\star}}^{\prime}c^{\pi})^{2}}=\sin\theta(c^{\star},c^{\pi}).$
To summarize, we have established that
$\mathcal{L}(c^{\pi},c^{\star})\leq\sin\theta(c^{\star},c^{\pi})$.

Step 4. We now construct an instance to show that, for any $c^{\star}$ and
$c^{\pi}$ with $\theta(c^{\star},c^{\pi})<\pi/2$, one may construct an
instance $\mathcal{X}$ and $f$ such that the regret is given by
$\sin\theta(c^{\star},c^{\pi})$. Let $\Pi_{c^{\pi}}(c^{\star})$ denote the
orthogonal projection of $c^{\star}$ onto $c^{\pi}$. Since
$\theta(c^{\star},c^{\pi})<\pi/2$ and both have unity norm, we have that
$\Pi_{c^{\pi}}(c^{\star})=\cos\theta(c^{\star},c^{\pi})\cdot c^{\pi}$. We now
define $r=c^{\star}-\Pi_{c^{\pi}}(c^{\star})$. Note that $r$ defines the
residual of the projection of $c^{\star}$ onto $c^{\pi}$. Therefore, it is
orthogonal to $c^{\pi}$ and $\|r\|=\sin\theta(c^{\star},c^{\pi})$. Then, by
summing the angles within the triangle, we have that
$\theta(c^{\star},c^{\pi})+\theta(r,c^{\star})+\pi/2=\pi$, and thus
$\theta(r,c^{\star})=\pi/2-\theta(c^{\star},c^{\pi})$.

Now we set $\delta=r/\|r\|$ and let nature pick ${f}(x)=x$ and ${{\cal
X}}=\\{x_{1},x_{2}\\}$ such that $x_{2}-x_{1}=\delta$. By construction,
$\delta$ is parallel to $r$ and must be orthogonal to $c^{\pi}$. Then,
$\delta^{\prime}c^{\pi}=(x_{2}-x_{1})^{\prime}c^{\pi}=0$, which implies that
$x_{1},x_{2}\in\psi(c^{\pi},{\cal X},f)$. Moreover,

$\delta^{\prime}c^{\star}=\frac{r^{\prime}c^{\star}}{\|r\|}=\frac{\|r\|\|c^{\star}\|\cos\theta(r,c^{\star})}{\|r\|}=\cos\theta(r,c^{\star})=\cos(\pi/2-\theta(c^{\star},c^{\pi}))=\sin\theta(c^{\star},c^{\pi}),$

completing the proof. ∎

###### Proof of Lemma 2.

If $C=\\{0\\}$, then, for any $\hat{c}\in S^{d}$, $\sup_{c\in
C}\theta(c,\hat{c})=0$ and any $\hat{c}\in S^{d}$ is a minimizer. Next we
consider the nontrivial case where $C\setminus\\{0\\}$ is nonempty.

Define the set
$\tilde{C}=\\{\tilde{c}\in\mathbb{R}^{d}~{}:~{}\tilde{c}=\frac{c}{\|c\|}\hbox{
for some }c\in C\setminus\\{0\\}\\}$ to be a set of normalized vectors from
$C\setminus\\{0\\}$. Then, the uncertainty angle of $C$ satisfies:

$\inf_{\hat{c}\in S^{d}}\sup_{c\in C}\theta(c,\hat{c})=\inf_{\hat{c}\in
S^{d}}\sup_{c\in C\setminus\\{0\\}}\theta(c,\hat{c})=\inf_{\hat{c}\in
S^{d}}\sup_{c\in
C\setminus\\{0\\}}\arccos\frac{c^{\prime}\hat{c}}{\|c\|}=\inf_{\hat{c}\in
S^{d}}\sup_{c\in\tilde{C}}\arccos c^{\prime}\hat{c},\quad$

where the first equality follows from the origin being a suboptimal solution
of the maximization $\sup_{c\in C}$ since $\theta(0,\hat{c})=0$ and $\theta$
is a non-negative function, the second equality follows from the definition of
an angle, and the third equality follows from replacing $C\setminus\\{0\\}$
with the normalized $\tilde{C}$.

Since $\arccos$ is a decreasing continuous function on $[-1,1]$, we have that
the uncertainty angle satisfies:

$\inf_{\hat{c}\in S^{d}}\sup_{c\in\tilde{C}}\arccos
c^{\prime}\hat{c}=\inf_{\hat{c}\in
S^{d}}\arccos\inf_{c\in\tilde{C}}c^{\prime}\hat{c}=\arccos\sup_{\hat{c}\in
S^{d}}\inf_{c\in\tilde{C}}c^{\prime}\hat{c},$

and the circumcenter $\hat{c}$ that optimizes the uncertainty angle is the
same one that solves the problem:

$\sup_{\hat{c}\in S^{d}}\inf_{c\in\tilde{C}}c^{\prime}\hat{c}.$ (B-3)

Define the function $g(\hat{c})=\inf_{c\in C}c^{\prime}\hat{c}$. Then, for any
$r>0$ and $u\in S^{d}$, we have that:

$g(\hat{c}+ru)=\inf_{c\in\tilde{C}}c^{\prime}(\hat{c}+ru)=\inf_{c\in\tilde{C}}\\{c^{\prime}\hat{c}+rc^{\prime}u\\},$

From the Cauchy-Schwarz inequality, we know that
$|c^{\prime}u|\leq\|c\|\cdot\|u\|=1$ since both $c$ and $u$ belong to $S^{d}$.
This implies that $-r\leq rc^{\prime}u\leq r$. Then,

$g(\hat{c})-r\leq g(\hat{c}+ru)\leq
g(\hat{c})+r\implies|g(\hat{c}+ru)-g(\hat{c})|\leq r,$

and we have that $g$ is a continuous function in $\mathbb{R}^{d}$. Therefore,
the problem $\sup_{\hat{c}\in S^{d}}g(\hat{c})$ from Eq. (B-3) is an
optimization problem with a continuous objective function over a compact
space. By the Weierstrass theorem, the sup is attained. Since the maximizer of
Eq. (B-3) is also the minimizer of the uncertainty angle, the infimum of that
problem (the circumcenter) is also attained.

Now we prove uniqueness under the assumption that $\alpha(C)<\pi/2$. Suppose
for a moment that the circumcenter is not unique and that $\hat{c}_{1}$ and
$\hat{c}_{2}$ are two distinct optimal solutions of Eq. (B-3). We will show
that we can construct a new solution $\hat{c}_{3}$ which is strictly better
than $\hat{c}_{1}$ and $\hat{c}_{2}$, leading to a contradiction.

Let $\hat{c}_{3}=(\hat{c}_{1}+\hat{c}_{2})/2$. First we argue that
$\hat{c}_{3}\neq 0$. If $\hat{c}_{3}=0$, this would imply that
$\hat{c}_{1}=-\hat{c}_{2}$. However, Since $\alpha(C)<\pi/2$, then, it must be
the case that $c^{\prime}\hat{c}_{1}>0$, for all $c\in C\setminus\\{0\\}$ and
$c^{\prime}\hat{c}_{2}>0$, for all $c\in C\setminus\\{0\\}$, which implies
that $c\in C\setminus\\{0\\}$ is empty, violating the assumption of the lemma.
Thus, $\|\hat{c}_{3}\|>0$. We also have that $\|\hat{c}_{3}\|<1$ since
$\hat{c}_{3}$ is a convex combination of two distinct vectors on the unit
sphere.

Let $z$ be the optimal value of Eq. (B-3), i.e.,
$z=\inf_{c\in\tilde{C}}c^{\prime}\hat{c}_{1}=\inf_{c\in\tilde{C}}c^{\prime}\hat{c}_{2}$.
Then,

$\displaystyle z$
$\displaystyle=\frac{1}{2}\inf_{c\in\tilde{C}}c^{\prime}\hat{c}_{1}+\frac{1}{2}\inf_{c\in\tilde{C}}c^{\prime}\hat{c}_{2}\stackrel{{\scriptstyle(a)}}{{<}}\frac{\frac{1}{2}\inf_{c\in\tilde{C}}c^{\prime}\hat{c}_{1}+\frac{1}{2}\inf_{c\in\tilde{C}}c^{\prime}\hat{c}_{2}}{\|\hat{c}_{3}\|}\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\inf_{c\in\tilde{C}}c^{\prime}\left(\frac{1}{2}\hat{c}_{1}+\frac{1}{2}\hat{c}_{2}\right)}{\|\hat{c}_{3}\|}=\inf_{c\in\tilde{C}}c^{\prime}\frac{\hat{c}_{3}}{\|\hat{c}_{3}\|},$

where $(a)$ follows from $\|\hat{c}_{3}\|<1$ and $(b)$ follows from combining
two infinimums. Since ${\hat{c}_{3}}/{\|\hat{c}_{3}\|}$ is a feasible solution
of Eq. (B-3) and its objective value is strictly above $z$, this would violate
the optimality of $\hat{c}_{1}$ and $\hat{c}_{2}$. This is a contradiction,
and the circumcenter must be unique. ∎

###### Proof of Theorem 1.

Upper bound. We construct the upper bound by showing that the objective
function from Eq. (4) is bounded by a function of $\alpha(C)$ for any
potential knowledge set $C$, and then argue that the same bound still applies
when we consider the worst-case $C$ within $\Lambda(\bar{\alpha})$.

We start by showing that for any policy $c^{\pi}\in\mathcal{P}^{\prime}$, we
can bound the objective function from Eq. (4) using the worst-case regret loss
function $\mathcal{L}$ for specific choices of nature
$(c^{\star},\mathcal{X},f)$, defined in Eq. (8). The following inequality
holds for any knowledge set $C\subseteq S^{d}$:

$\displaystyle\inf_{\pi\in{\cal P}}\>\sup_{{\cal
X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in
C}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\inf_{\pi\in\mathcal{P}^{\prime}}\>\sup_{{\cal
X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in
C}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\inf_{c^{\pi}\in
S^{d}}\>\sup_{{\cal X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in
C}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\inf_{c^{\pi}\in
S^{d}}\>\sup_{c^{\star}\in C}\>\mathcal{L}(c^{\pi},c^{\star}).$ (B-4)

where $(a)$ follows from restricting $\pi$ to ${\cal P}^{\prime}$, $(b)$
follows from representing $\pi\in\mathcal{P}^{\prime}$ in terms of its cost
vector $c^{\pi}$, and $(c)$ follows from the definition of $\mathcal{L}$ (it
would be an equality if $x^{\pi}$ were unique).

Let us define:

$\displaystyle g(x)$ $\displaystyle=$ $\displaystyle\begin{cases}\sin
x&\mbox{if }0\leq x<\pi/2,\\\ 1&\mbox{if }x\geq\pi/2.\end{cases}$

Lemma 1 shows that
$\mathcal{L}(c^{\pi},c^{\star})=g(\theta(c^{\star},c^{\pi}))$. Combining with
Eq. (B), we have:

$\displaystyle\inf_{\pi\in{\cal P}}\>\sup_{{\cal
X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in
C}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\leq$ $\displaystyle\inf_{c^{\pi}\in S^{d}}\>\sup_{c^{\star}\in
C}\>g(\theta(c^{\star},c^{\pi}))$ $\displaystyle=$ $\displaystyle
g\left(\inf_{c^{\pi}\in S^{d}}\>\sup_{c^{\star}\in
C}\>\theta(c^{\star},c^{\pi})\right)=g(\alpha(C)),$

where the first equality follows from $g(\cdot)$ being nondecreasing and
continuous, and the second equality follows from the definition of the
uncertainty angle. (When we replace the infinimum with the uncertainty angle
above, we are implicitly using the circumcenter policy.)

Since the set bound above holds for any set $C\in\Lambda(\bar{\alpha})$, we
have:

$\sup_{C\in\Lambda(\bar{\alpha})}\>\inf_{\pi\in{\cal P}}\sup_{{\cal
X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in
C}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}\leq\sup_{C\in\Lambda(\bar{\alpha})}g(\alpha(C))=g\left(\sup_{C\in\Lambda(\bar{\alpha})}\alpha(C)\right)=g(\bar{\alpha}),$

where the first equality again follows from $g(\cdot)$ being nondecreasing and
continuous, and the second equality follows from the definition of
$\Lambda(\bar{\alpha})$.

Lower bound. For the lower bound, we construct instances of the problem where
any policy incurs at least the regret $g(\bar{\alpha})$. We first consider the
case where $\bar{\alpha}\leq\pi/2$. Let
$e=\frac{1}{\sqrt{d}}(1,\cdots,1)^{\prime}$ and $\tilde{C}=\\{c\in
S^{d}:\>\theta(e,c)\leq\bar{\alpha}\\}$, which is the intersection between a
sphere and the revolution cone with axis $e$ and aperture angle of
$\bar{\alpha}$. Note that if $\bar{\alpha}=\pi/2$ there is no revolution cone,
but it suffices to consider the halfspace $\tilde{C}=\\{c\in
S^{d}:\>c^{\prime}e\leq 0\\}$. Moreover, let ${f}(x)=x$ and ${{\cal
X}}=\\{x_{1},x_{2}\\}$ such that $\delta=x_{2}-x_{1}$ is orthogonal to $e$ and
$\|\delta\|=1$.

Define $c_{1}^{\star}=\sin\bar{\alpha}\cdot\delta+\cos\bar{\alpha}\cdot e$. We
now argue that $c_{1}^{\star}$ belongs to $\tilde{C}$. We first show that
$c_{1}^{\star}\in S^{d}$:

$\|c_{1}^{\star}\|^{2}=\sin^{2}\bar{\alpha}\cdot\|\delta\|^{2}+\cos^{2}\bar{\alpha}\cdot\|e\|^{2}=\sin^{2}\bar{\alpha}+\cos^{2}\bar{\alpha}=1,$

where the first equality follows from $\delta$ and $e$ being orthogonal
vectors, and the second equality follow from $\delta$ and $e$ having norm 1.
We now show that $\theta(e,c_{1}^{\star})=\bar{\alpha}$:

$\theta(e,c_{1}^{\star})=\arccos\frac{e^{\prime}c_{1}^{\star}}{\|e\|\|c_{1}^{\star}\|}=\arccos{e^{\prime}c_{1}^{\star}}=\arccos{\cos\bar{\alpha}}=\bar{\alpha},$

where the second equality follows from $e$ and $c_{1}^{\star}$ having norm 1,
and the third equality follows from $\delta$ and $e$ being orthogonal.

We now construct a second vector in $\tilde{C}$,
$c_{2}^{\star}=-\sin\bar{\alpha}\cdot\delta+\cos\bar{\alpha}\cdot e$. By the
same argument as above, $c_{2}^{\star}$ also belongs to $\tilde{C}$. Note that
$x_{1}$ is the optimal action if $c_{1}^{\star}$ is the true cost and $x_{2}$
is the optimal action if $c_{2}^{\star}$ is the true cost since
$(x_{2}-x_{1})^{\prime}c_{1}^{\star}=\sin(\bar{\alpha})\geq 0$ and
$(x_{2}-x_{1})^{\prime}c_{2}^{\star}=-\sin(\bar{\alpha})\leq 0$. Since for any
policy $\pi\in{\cal P}$ the decision-maker must choose either $x_{1}$ or
$x_{2}$, we have:

$\displaystyle\sup_{C\in\Lambda(\bar{\alpha})}\inf_{\pi\in{\cal P}}\sup_{{\cal
X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in
C}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\inf_{\pi\in{\cal
P}}\sup_{{\cal
X}\in\mathcal{B},\>f\in\mathcal{F},\>c^{\star}\in\tilde{C}}\>\bigl{(}f(x^{\pi})-f(x^{\star})\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\inf_{x^{\pi}\in\\{x_{1},x_{2}\\}}\sup_{\>c^{\star}\in\tilde{C}}\>\bigl{(}x^{\pi}-x^{\star}\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\inf_{x^{\pi}\in\\{x_{1},x_{2}\\}}\sup_{\>c^{\star}\in\\{c_{1}^{\star},c_{2}^{\star}\\}}\>\bigl{(}x^{\pi}-x^{\star}\Bigr{)}^{\prime}c^{\star}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\min\\{(x_{2}-x_{1})^{\prime}c_{1}^{\star},(x_{1}-x_{2})^{\prime}c_{2}^{\star}\\},$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}\min\\{\delta^{\prime}c_{1}^{\star},-\delta^{\prime}c_{2}^{\star}\\}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{=}}\min\\{\sin\bar{\alpha},\sin\bar{\alpha}\\}=\sin\bar{\alpha}.$

where $(a)$ follows from the choice of $\tilde{C}$ from the set
$\Lambda(\bar{\alpha})$, $(b)$ follows from our choice of instance $({\cal
X},f)$, $(c)$ follows from restricting the choice of $c^{\star}\in C$ to
$\\{c_{1}^{\star},c_{2}^{\star}\\}$, $(d)$ follows from the fact that $x_{1}$
is optimal for $c_{1}^{\star}$ and $x_{2}$ is optimal for $c_{2}^{\star}$,
$(e)$ follows from the definition of $\delta$, and $(f)$ follows from the
definitions of $c_{1}^{\star}$ and $c_{2}^{\star}$ and the fact that $\delta$
and $e$ are orthogonal. This completes the argument for the case where
$\bar{\alpha}\leq\pi/2$.

Finally, we now consider the case where $\bar{\alpha}>\pi/2$. Since $C$ is
weakly geodesically convex, this implies that $C=S^{d}$ since otherwise we
could construct unique minimal-length arcs between points in $C$ that do not
go through $C$. Let us consider the instance where ${\cal X}$ is a
$d$-dimensional sphere of diameter 1 and $f(x)=x$. No matter the choice of
action $x$, nature can select $c^{\star}=2x$ (the 2 in front of $x$ is a
normalization needed because $\|x\|=1/2)$. Given nature’s choice of
$c^{\star}$, the optimal action would have been $x^{\star}=-c^{\star}/2=-x$.
Therefore, the regret incurred can be as large as
$(x-x^{\star})^{\prime}c^{\star}=2x^{\prime}(2x)=4\|x\|^{2}=1$. This completes
the proof.∎

###### Proof of Theorem 2.

Let $\pi=\pi_{greedy}$ and let $e_{i}$ denote the $i$-th vector of the
canonical basis in $\mathbb{R}^{d}$. For $c\in\mathbb{R}^{d}$, we use
$c_{[i]}$ to denote the $i$-th entry of the vector $c$.

The proof strategy is organized as follows. In step 1, we define a useful
family of sets that will characterize our sequence of knowledge sets. In step
2, we construct choices of sets $\mathcal{X}_{t}$ and context functions
$f_{t}$ so that the greedy policy implies that the sequence of knowledge sets
$C(\mathcal{I}_{t})$ always belongs to the family of sets that we defined in
step 1. For this construction, we will focus on a 3-dimensional case, i.e.,
$d=3$. In step 3, we show that the regret in every time period must be
uniformly bounded away from zero regardless of the time horizon, leading to
the linear regret.

Step 1. We first define a family of sets that will be central in the
construction of instances with linear regret.

Define $h_{1}=(2\sin^{2}\bar{\alpha},-\sin 2\bar{\alpha},\sin 2\bar{\alpha})$,
$h_{2}=(2\sin^{2}\bar{\alpha},-\sin 2\bar{\alpha},-\sin 2\bar{\alpha})$ and
$h_{3}=(-\varepsilon,1,0)$. Consider the following family of sets indexed by
$\bar{\alpha}$ and $\varepsilon$ with $0<\bar{\alpha}<\pi/2$ and
$0\leq\varepsilon\leq(\tan\bar{\alpha})/2$:

$C_{\varepsilon,\bar{\alpha}}=\\{c\in\mathbb{R}^{d}:\;h_{1}^{\prime}c\geq
0\\}\cap\\{c\in\mathbb{R}^{d}:\;h_{2}^{\prime}c\geq
0\\}\cap\\{c\in\mathbb{R}^{d}:\;h_{3}^{\prime}c\geq 0\\}\cap S^{d}.$

Note that $C_{\varepsilon,\bar{\alpha}}$ is the intersection of a polyhedral
cone with the unit sphere. Using the halfpsaces defined by $h_{1}$, $h_{2}$
and $h_{3}$, we can compute the generators of such a polyhedral cone. The
generators of the cone are
$g_{1}=(1,\varepsilon,\varepsilon-\tan\bar{\alpha})$,
$g_{2}=(1,\varepsilon,\tan\bar{\alpha}-\varepsilon)$ and
$g_{3}=(\cos\bar{\alpha},\sin\bar{\alpha},0)$. For simplicity, the generators
were not normalized. The set $C_{\varepsilon,\bar{\alpha}}$ is always nonempty
if $\varepsilon\leq\tan\bar{\alpha}$ and $\bar{\alpha}<\pi/2$ and we fix
$c^{\star}=g_{3}=(\cos\bar{\alpha},\sin\bar{\alpha},0)$. Using Definition 2,
one can also show that
$\hat{c}(C_{\varepsilon,\bar{\alpha}})=(1,\varepsilon,0)$. In Figure 6(a), we
depict an example of initial knowledge set $C_{0}$ for $\varepsilon=0$ and
$\bar{\alpha}=\pi/4$.

Step 2. Fix $0<\bar{\alpha}<\pi/2$ and define a sequence of instances as
follows. We let $C_{0}=C_{0,\bar{\alpha}}$ (Figure 6(a) depicts the set
$C_{0}$ for $\bar{\alpha}=\pi/4$). Suppose that $f_{t}$ is the identity for
all $t\geq 1$ and let

$\displaystyle\varepsilon_{1}=\frac{\tan\bar{\alpha}}{2T},\qquad\varepsilon_{t}=t\varepsilon_{1},\quad
t\geq 2,$ $\displaystyle{\cal X}_{t}=\\{\bar{x}_{t},0\\},\quad t\geq 1,$

where

$\bar{x}_{t}=(e_{2}-\varepsilon_{t}e_{1})/\|e_{2}-\varepsilon_{t}e_{1}\|.$

In Figure 6(b), we provide an illustration for $\bar{\alpha}=\pi/4$ and $T$
taken to be 5, so $\varepsilon_{1}=0.1$.

(a)

(b)

Figure 6: In $(a)$, we depict the initial knowledge set $C_{0}$ and its
circumcenter. In $(b)$, we depict the first instance of the optimization
problem faced by the decision-maker and the true cost vector $c^{\star}$.

Next, we establish by induction on $t$ that, under the greedy circumcenter
policy, $C(\mathcal{I}_{t})=C_{\varepsilon_{t-1},\bar{\alpha}}$ for $t\geq 2$.
Note that the result is trivial for $t=1$ since
$C(\mathcal{I}_{t})=C_{0}=C_{0,\bar{\alpha}}$ by construction. Next we
establish the base case ($t=2$).

By definition (Eq. (5)) we have that

$C(\mathcal{I}_{2})=C_{0}\cap\\{c\in\mathbb{R}^{d}:c^{\prime}f_{1}(\bar{x}_{1})\leq
c^{\prime}f_{1}(x),\;\forall\;x\in{\cal X}_{1}\\}.$

Moreover, since $C(\mathcal{I}_{1})=C_{0,\bar{\alpha}}$, $f_{1}$ is the
identity and $\mathcal{X}_{1}=\\{\bar{x}_{1},0\\}$, we must have that
$\hat{c}(C(\mathcal{I}_{1}))=e_{1}$, $\psi(e_{1},f_{1},{\cal
X}_{1})=\bar{x}_{1}$ and $\psi(c^{\star},f_{1},{\cal X}_{1})=0$. Which leads
to

$C(\mathcal{I}_{2})=C_{0}\cap\\{c\in\mathbb{R}^{d}\;:\;-\varepsilon_{1}c_{[1]}+c_{[2]}\geq
0\\}=C_{\varepsilon_{1},\bar{\alpha}},$

and the base case is established. Next we show the induction step. Suppose
that the result holds for $t$. Then, the circumcenter of $C(\mathcal{I}_{t})$
is given by $(1,\epsilon_{t-1},0)$. Therefore, $\psi(c_{t}^{\pi},f_{t},{\cal
X}_{t})=\bar{x}_{t}$ and $\psi(c^{\star},f_{,}{\cal X}_{t})=0$, which leads to
the update:

$\displaystyle C(\mathcal{I}_{t+1})$
$\displaystyle=C(\mathcal{I}_{t})\cap\\{c\in\mathbb{R}^{d}\;:\;-\varepsilon_{t}c_{[1]}+c_{[2]}\geq
0\\}$
$\displaystyle=C_{0}\cap\\{c\in\mathbb{R}^{d}\;:\;-\varepsilon_{t-1}c_{[1]}+c_{[2]}\geq
0\\}\cap\\{c\in\mathbb{R}^{d}\;:\;-\varepsilon_{t}c_{[1]}+c_{[2]}\geq 0\\}$
$\displaystyle=C_{0}\cap\\{c\in\mathbb{R}^{d}\;:\;-\varepsilon_{t}c_{[1]}+c_{[2]}\geq
0\\}=C_{\varepsilon_{t},\bar{\alpha}},$

which concludes the proof by induction. Having established the above, we now
analyze the regret in each period $t$.

Step 3. From step 2, we have for every time $t$ that
$C(\mathcal{I}_{t+1})=C_{\varepsilon_{t},\bar{\alpha}}$,
$\hat{c}(C(\mathcal{I}_{t+1}))=\frac{1}{\sqrt{1+\varepsilon_{t}^{2}}}(1,\varepsilon_{t},0)$
and the regret at period $t$ is given by

${\delta_{t}^{\pi}}^{\prime}c^{\star}=\frac{(-\epsilon_{t}e_{1}+e_{2})^{\prime}(\cos\bar{\alpha},\sin\bar{\alpha},0)}{\sqrt{1+\varepsilon_{t}^{2}}}=\frac{\sin\bar{\alpha}-\varepsilon_{t}\cos\bar{\alpha}}{\sqrt{1+\varepsilon_{t}^{2}}}\geq\frac{T\sin\bar{\alpha}-(t/2T)\sin\bar{\alpha}}{\sqrt{2}}\geq\frac{\sin\bar{\alpha}}{4},$

where the first inequality follows from the fact that $\varepsilon^{2}\leq 1$.
Therefore, the cumulative regret must be $\Omega(T)$.

In Figure 7(a), we can see the initial knowledge set $C_{0}$ for
$\bar{\alpha}=\pi/4$. In Figure 7(b), we have the updated knowledge set
$C(\mathcal{I}_{2})=C_{\varepsilon,\bar{\alpha}}$ after solving the first
optimization instance. In Figure 7(c) we have the final set after collecting
the feedback of the last time period $T=5$. No matter the horizon $T$, nature
can always adjust $\epsilon_{1}$ as a function of $\bar{\alpha}$ and $T$ in in
order to ensure that the updates are not enough to make the circumcenter and
the true cost vector sufficiently close to each other.

(a)

(b)

(c)

Figure 7: In $(a)$ we have the initial knowledge set and the first instance of
the optimization problem. In $(b)$, the updated set $C(\mathcal{I}_{2})$, the
new circumcenter $\hat{c}(C(\mathcal{I}_{2}))$, the true cost vector and the
previous action $\bar{x}_{1}$. In $(c)$, the knowledge set after collecting
the feedback of period $T$.

∎

###### Proof of Lemma 3.

Lemma 3 is a direct application of a more general result, described in Lemma
B-1, stated and proved in Section B.1. In particular, if $t$ is a cone update
period, we take $p=d$, $\eta=0$, $\delta=\delta_{t}^{\pi}$ and
$E(W,U)=E(W_{t},U_{t})$. We have that
${\delta}^{\prime}\hat{c}(E(W_{t},U_{t}))={\delta_{t}^{\pi}}^{\prime}c_{t}^{\pi}\leq
0$ where the inequality holds by definition of the effective difference
$\delta_{t}^{\pi}$ (Eq. 11) and the circumcenter policy applied to ellipsoidal
cones. ∎

###### Proof of Proposition 1.

Note that the circumcenter of $E(W,U)$ is $Ue_{1}$. Let $E_{H}(W)=E(W)\cap H$,
where $H=\\{c\in\mathbb{R}^{d}:\;c^{\prime}e_{1}=1\\}$. Next, recall that for
any $c\in E(W)\setminus\\{0\\}$, the first component is always greater than
zero. Then,

$\alpha(E(W,U))\>=\>\sup_{c\in E(W,U)}\theta(c,Ue_{1})=\sup_{c\in
E(W)}\theta(c,e_{1})=\sup_{c\in
E(W)\setminus\\{0\\}}\theta(c,e_{1})=\sup_{c\in E_{H}(W)}\theta(c,e_{1}),$

where the second equality follows from the the fact that angles are preserved
by orthonormal transformations, the third equality follows from the
suboptimality of $\\{0\\}$ and the last equality follows from the fact that
scaling a vector by a positive constant does not affect the angle. Moreover,
for every $c\in E_{H}(W)$, we have that

$\tan\theta(c,e_{1})=\tan\arccos\frac{c^{\prime}e_{1}}{\|c\|}=\tan\arccos\frac{1}{\|c\|},$

where the first equality follows from the definition of an angle and the
second one follows from $E_{H}(W)\subset H$. Hence,

$\tan\theta(c,e_{1})=\sqrt{\|c\|^{2}-1}=\|c_{[2:d]}\|,$

where we used the trigonometric identity $\tan\arccos
x=\frac{\sqrt{1-x^{2}}}{x}$ for $x\in[0,\pi/2)$. Using the fact that
$E_{H}(W)$ is an ellipsoid one gets that
$\|c_{[2:d]}\|\leq\sqrt{\lambda_{\max(M)}}$ and the inequality is tight for
some $c\in E_{H}(W)$. Since $\tan(\cdot)$ is continuous and monotone
increasing on $[0,\pi/2)$, we get

$\alpha(E(W,U))=\sup_{c\in E_{H}(W)}\theta(c,e_{1})=\sup_{c\in
E_{H}(W)}\arctan\left(\tan\theta(c,e_{1})\right)=\arctan\sqrt{\lambda_{\max(M)}}.$

This completes the proof.

∎

###### Proof of Lemma 4.

Consider any $c\in E(W_{t},U_{t})\cap S^{d}$. Let $\tilde{c}=U_{t}^{-1}c$ and
$\tilde{\delta}_{t}^{\pi}=U_{t}^{-1}\delta_{t}^{\pi}$. Recalling that for an
orthonormal matrix $U$, $U^{-1}=U^{\prime}$, the regret in period $t$ if the
true underlying cost is $c$ is given by

$\displaystyle{\delta^{\pi}_{t}}^{\prime}c$ $\displaystyle=$
$\displaystyle{\delta^{\pi}_{t}}^{\prime}U_{t}U_{t}^{-1}c\>=\>{(U_{t}^{-1}{\delta^{\pi}_{t}})}^{\prime}U_{t}^{-1}c\>=\>(\tilde{\delta}_{t}^{\pi})^{\prime}\tilde{c}.$

Note that $\tilde{c}\in E(W_{t})\cap S^{d}$ and hence
$\tilde{c}_{[1]}\in(0,1]$. Let $\tilde{\nu}=\tilde{c}_{[2:d]}/\tilde{c}_{[1]}$