# Combining Online Learning and Offline Learning for Contextual Bandits with
Deficient Support

Hung Tran-The, Sunil Gupta, Thanh Nguyen-Tang, Santu Rana, Svetha Venkatesh
Applied Artificial Intelligence Institute
Deakin University, Australia
Correspondence to: Hung Tran-The<EMAIL_ADDRESS>
###### Abstract

We address policy learning with logged data in contextual bandits. Current
offline-policy learning algorithms are mostly based on inverse propensity
score (IPS) weighting requiring the logging policy to have _full support_ i.e.
a non-zero probability for any context/action of the evaluation policy.
However, many real-world systems do not guarantee such logging policies,
especially when the action space is large and many actions have poor or
missing rewards. With such _support deficiency_ , the offline learning fails
to find optimal policies. We propose a novel approach that uses a hybrid of
offline learning with online exploration. The online exploration is used to
explore unsupported actions in the logged data whilst offline learning is used
to exploit supported actions from the logged data avoiding unnecessary
explorations. Our approach determines an optimal policy with theoretical
guarantees using the minimal number of online explorations. We demonstrate our
algorithms’ effectiveness empirically on a diverse collection of datasets.

##  1 Introduction

Many interactive systems (e.g., recommender systems, search engines) can be
modeled as contextual bandit problems where the learner repeatedly observes a
context (e.g., user profile, query), takes an action (e.g., recommended
product) and observes a reward (e.g., purchase, click) for the chosen action.
The goal of such interactive systems is to collect as much reward as possible.

When logged data is available and acquiring new data is expensive, offline
contextual bandit methods that leverage offline data without further online
exploration are an ideal approach. Several solutions follow this approach
(e.g., (Dudík et al., 2011; Strehl et al., 2010; Swaminathan et al., 2017;
Wang et al., 2017; Kato et al., 2020)). However, most current solutions
including the regression-based direct modeling (DM), the inverse propensity
score (IPS) (Horvitz and Thompson, 1952), and the doubly robust (DR) (Dudík et
al., 2011) estimators are unsuitable for real-world applications. The DM
approach learns a reward model and estimates the value of an evaluation
policy. This estimate is usually biased because of model misspecification,
which is difficult to correct without the knowledge of the evaluation policy.
IPS uses importance weighting to correct for the proportions of actions in
offline data and is guaranteed to be unbiased (Strehl et al., 2010; Dudík et
al., 2011; Farajtabar et al., 2018; Swaminathan and Joachims, 2015b; Xie et
al., 2019). DR can combine the two estimators and achieve unbiased estimates
if only if one of the estimators is unbiased (Dudík et al., 2011).
Unfortunately, IPS is only unbiased if the logging policy has full support,
that is, all actions have nonzero probability of being selected under the
logging policy. Full support, however, does not exist in most real-world
systems, especially when the action space is large and many actions have poor
rewards. For example, in a recommender system with a large catalogue, only a
small percentage of the items (actions) are in the support of the logging
policy. This renders off-policy learning methods that rely on IPS unusable,
e.g. current off-policy learning algorithms such as the counterfactual
estimator based algorithm (Swaminathan and Joachims, 2015b), the CAIPWL
estimator based algorithm (Zhou et al., 2018) and MLIPS estimator (Xie et al.,
2019) unusable, as being based on IPS, they require full support.

With such support deficiency, the unbiasedness of both IPS and DM methods
breaks down. Sachdeva et al. (2020) approaches the off-policy contextual-
bandit learning by either seeking solutions in a restricted search space close
to supported actions, or learn rewards of unsupported actions from logging
policy by regression extrapolation. However, in such a restricted search
space, we may only find only suboptimal solutions especially when the optimal
actions are far from the supported actions. Also, learning rewards of
unsupported actions is inefficient because we have no any information about
unsupported actions. In the setting where online exploration is possible
(though possibly expensive), a natural approach to resolve the support
deficiency is to acquire new data to inform about the unsupported actions in
the offline data. This idea is surprisingly unexplored. How to efficiently
resolve support deficiency in offline learning with online data and how such a
hybrid approach can be more efficient than pure online learning with
contextual bandits (e.g., (Chu et al., 2011; Agrawal and Goyal, 2013; Agarwal
et al., 2014)) remain open questions.

In this paper, we address the deficiency support problem for contextual
bandits by combining offline and online learning. The online exploration is
used to explore unsupported actions in the logged data whilst offline-policy
learning is used to exploit the supported actions from the logged data
avoiding unnecessary explorations. Our approach can efficiently find the
optimal policy with theoretical guarantees. Our main contributions are as
follows:

  * •

We study the deficiency support for contextual bandits from a novel hybrid
perspective combining offline and online learning;

  * •

We introduce two algorithms. The first algorithm leverages reward models
learned from offline data to reduce the number of online explorations (Section
4.2). The second algorithm improves the efficiency of the first one to further
reduce the number of online explorations by exploiting "good" context-action
pairs in offline data i.e., the reward corresponding to this context-action
pair is approximately optimal. (Section 4.3);

  * •

We provide a unifying analysis for our hybrid approach that generalizes the
analysis of either online or offline learning; in particular, we show that
both of our proposed algorithms obtain sublinear regrets;

  * •

Finally, we demonstrate our algorithms’ effectiveness empirically on a diverse
collection of data sets in Section 5.

##  2 Related Works

The contextual-bandit learning can be viewed as off-policy learning in the
reinforcement learning(RL) (Levine et al., 2020) which considers learning
optimal policies in the sequential decision-making setting. Similar to the
works of Sachdeva et al. (2020) in contextual bandit, Liu et al. (2020)
proposes safe learning algorithms based on policy iteration and value
iteration by restricting the policy space. In linear MDP, Jin et al. (2020)
show that an offline learning method following the pessimism principle finds
the optimal policy in sublinear time in linear MDP when the offline data and
the evaluation well explore the action and context space. Though the "well-
explored" condition in Jin et al. (2020) is weaker than full support
condition, the pessimism principle stills fail in the presence of deficient
support in disjoint linear models where the parameters are not shared among
different actions.

Combining offline learning and online learning has been also studied but for
the purposes rather than resolving the support deficiency problem, e.g., in
multi-armed bandits (Shivaswamy and Joachims, 2012), in latent bandits (Zhou
and Brunskill, 2016; Hong et al., 2020), in confounded bandits (Tennenholtz et
al., 2020), in causal inference (Ye et al., 2020), and in online fine-tuning
(Levine et al., 2020). In our knowledge, we are the first to address the
support deficiency problem by combining online and offline learning.

##  3 Problem Setting

###  3.1 Contextual Bandit

We consider the contextual bandit problem. Formally, we define by
$\mathcal{A}=\\{1,2,...,K\\}$ the set of actions, and a learner interacts with
the environment in discrete iteration $t=1,2,...$. In iteration $t$:

  1. 1.

The environment outputs a context $x_{t}\in\mathcal{X}\subset\mathbb{R}^{d}$
sampled from a unknown distribution $P_{x}$.

  2. 2.

Based on observed payoffs in previous trials and the current context $x_{t}$,
the learner chooses an action $a_{t}\in\mathcal{A}$, and receives payoff
$r_{t}$. It is important to note here that no feedback information is observed
for unchosen actions $a\not=a_{t}$.

  3. 3.

The learner then improves its action-selection strategy using all information
$\\{(x_{i},a_{i},r_{i})\\}$.

We consider a disjoint linear model of reward in the form $r_{x,a}=\langle
x,\theta^{*}_{a}\rangle+\eta$, where $\theta^{*}_{a}$ is _unknown_ parameter
vector of action $a$, and $\eta$ is a $\sigma$-subgaussian random noise. This
model is _disjoint_ in the sense that the parameters are not shared among
different actions (Li et al., 2010).

Given a space $\Pi$ of policies $\pi:\mathcal{X}\rightarrow\mathcal{A}$, we
define the value of any policy $\pi\in\Pi$ as $R(\pi)=\mathbb{E}_{x\sim
P_{x}}\mathbb{E}_{a\sim\pi(x)}[r_{x,a}]$. The goal of the policy learning
algorithm is to find an optimal policy $\pi^{*}$ that has the maximum value
$R(\pi)$.

In this work, we assume that we have an offline dataset
$S=\\{x^{\mu}_{i},a^{\mu}_{i},r^{\mu}_{i}\\}_{i=1}^{n}$ in which the contexts
$\\{x^{\mu}_{i}\\}_{i=1}^{n}$ are i.i.d sampled from the distribution $P_{x}$,
the actions $\\{a^{\mu}_{i}\\}_{i=1}^{n}$ are generated by some fixed behavior
policy, denoted by $\mu$ which is a mapping from context $x\in\mathcal{X}$ to
a probability over actions; the corresponding rewards
$\\{r^{\mu}_{i}\\}_{i=1}^{n}$ are generated by the same reward model
$r^{\mu}_{i}=\langle x^{\mu}_{i},\theta^{*}_{a^{\mu}_{i}}\rangle+\eta_{i}$.

####  3.1.1 Performance Measure

We measure the performance of algorithms based on (1) the number of online
explorations given the same set of contexts and (2) the following regret
$R_{T}$.

Assume that the learner is allowed to interact with the environment in $T$
times, the first goal of the learner is to select $T$ contexts
$\\{x_{1},x_{2},...,x_{T}\\}$ from the environment and take appropriate
actions to maximize the cumulative rewards $\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{a_{t}}\rangle$, where $a_{t}$ is the chosen action
corresponding to context $x_{t}$ at iteration $t$. It is equivalent to
minimize the regret $R_{T}=\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$, where
$\pi^{*}(x)\in\text{argmax}_{a\in\mathcal{A}}\langle x,\theta^{*}_{a}\rangle$.

In the presence of offline data, algorithms do not always need to take actions
and call reward functions while interacting with the environment. For example,
when the reward model of an action is learned well from offline data by some
manner, the learner can predict the received reward when if that action is
chosen and hence avoids calling reward functions unnecessarily which may be
expensive/risky in many applications (See our Algorithm 2). Thus, the second
goal of learner is to reduce efficiently reward callings. We note that we
distinguish between the interaction and the exploration. When we say that the
learner performs an _online exploration_ we mean it perform an action and
receive the reward function.

###  3.2 Support Deficiency

Given dataset $S$ from logging policy $\mu$, we are interested in estimating
the value of a policy $\pi$. The unbiasedness of an estimator is crucial for
policy learning. While this property is hard to be guaranteed by the DM
estimator, it can be guaranteed by the IPS estimator,
$\hat{R}_{IPS}(\pi)=\frac{1}{|S|}\sum_{i=1}^{|S|}\frac{\pi(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})}r^{\mu}_{i}$,
if full support between the target policy $\pi$ and the logging policy $\mu$
is satisfied:

######  Definition 1 (Full Support).

The logging policy $\mu$ is said to have full support for $\pi$ if for all
context-action pairs $(x,a)\in\mathcal{X}\times\mathcal{A}$, whenever
$\pi(a|x)>0$ we also have $\mu(a|x)>0$.

In this case, we have $\mathbb{E}_{S}[\hat{R}_{IPS}]=R(\pi)$. This property is
needed for not only IPS, but also for similar estimators like counterfactual
estimator (Swaminathan and Joachims, 2015b), SNIPS (Swaminathan and Joachims,
2015a), CAIPWL (Zhou et al., 2018), MLIPS (Xie et al., 2019), CAB (Su et al.,
2019). However, this condition may not be feasible in many real-world systems,
especially if the action space is large and many actions have poor or missing
reward. When the full support requirement is violated, we call it _deficient
support_. To quantify how support deficient a logging policy is, we denote the
set of _unsupported actions_ for context $x$ under a policy $\pi$ as

$\mathcal{U}(x,\pi)=\\{a\in\mathcal{A}|\pi(a|x)=0\\}.$

We note that sets of unsupported actions of different contexts may be
different. Deficient support happens when
$\mathcal{U}(x,\mu)\cap\mathcal{U}^{c}(x,\pi)\not=\emptyset$, where
$\mathcal{U}^{c}$ is the complement of $\mathcal{U}$. The larger the
intersection set, the more deficient is the support for the context $x$. In
the support deficiency, the bias of the IPS is then characterized by the
expected reward on the unsupported actions.

######  Proposition 1 (Proposition 1 of (Sachdeva et al., 2020)).

The bias of an estimator $\hat{R}_{IPS}(\pi)$ for target policy $\pi$ is equal
to the expected reward on the unsupported action sets, i.e.,

$\text{bias}(\hat{R}_{IPS}(\pi))=\mathbb{E}_{S}[\hat{R}_{IPS}(\pi)]-R(\pi)=\mathbb{E}_{x}[-\sum_{a\in\mathcal{U}(x,\mu)}\pi(a|x)\delta(x,a)],$

where $R(\pi)$ is the true value of $\pi$ which is defined as
$R(\pi)=\mathbb{E}_{x\in\mathcal{X}}\mathbb{E}_{a\in\pi(a|x)}[r(x,a)]$, and
$\delta(x,a)=\mathbb{E}_{S}[r(x,a)|x,a]$.

In fact, it is not possible to eliminate the bias only with the offline data
when the set $\mathcal{U}(x,\mu)\cap\mathcal{U}^{c}(x,\pi)$ is large except
one special case where all the reward models are learnt. We mention this in
Remark 2.

##  4 Policy Learning Algorithms

In this section, we provide algorithms for learning the optimal policy in
presence of support deficiency. All proofs are provided in the Supplementary
Material.

###  4.1 mOFUL Algorithm

The simplest idea is to design an online learning where there is no
exploitation of offline data. We adapt the OFUL algorithm (Abbasi-yadkori et
al., 2011) to our setting where each action $a$ has an unknown particular
parameter $\theta_{a}$ instead only one parameter across all actions
$\theta^{*}$ as in the original paper. For each action $a$, the algorithm
maintains a confidence interval $C_{t,a}\subseteq\mathbb{R}^{d}$ at each
iteration $t$ for its parameter $\theta^{*}_{a}$ such that this interval
contains $\theta^{*}_{a}$ with high probability. Assume that
$(x_{1},a_{1},r_{1}),...,(x_{t},a_{t},r_{t})$ are context-action-reward
triples generated by the algorithm up to iteration $t$. Given an action $a$,
we denote by $i_{1},..,i_{t_{a}}$ iterations up to $t$ in which $a$ is chosen
by the algorithm. Let $\hat{\theta}_{t,a}$ be the least-squares estimate of
$\theta^{*}_{a}$ with regularization parameter $\lambda>0$:

$\displaystyle\hat{\theta}_{t,a}=(X^{T}_{t,a}X_{t,a}+\lambda
I)^{-1}X^{T}_{t,a}Y_{t,a}$ (1)

where matrix $X_{t,a}$ rows are $x^{T}_{i_{1}},...,x^{T}_{i_{t}}$,
$Y_{t,a}=(r_{i_{1}},...,r_{i_{t}})^{T}$; $x^{T}$ and $X^{T}$ denotes the
transpose of a vector $x$ and matrix $X$ respectively. Based on
$\hat{\theta}_{t,a}$, the interval $C_{t,a}$ is defined as follows:

$\displaystyle
C_{t,a}=\\{\theta\in\mathbb{R}^{d}:||\hat{\theta}_{t,a}-\theta||_{\overline{V}_{t,a}}\leq\beta_{t}\\},$
(2)

where $\overline{V}_{t,a}=\lambda
I+\sum_{i=1}^{t}x_{i}x_{i}^{T}\mathbf{1}(a_{i}=a)$ and
$\sqrt{\beta_{t}(\delta)}=\sigma\sqrt{d\text{log}(\frac{K-(1+tS^{2}_{x}/\lambda)}{\delta})}+\lambda^{1/2}S_{\theta}$;
$S_{x}$ and $S_{\theta}$ are the upper bounds on $||x||$ and
$||\hat{\theta}_{t,a}||$ respectively. $\textbf{1}(.)$ is an indicator
function evaluating to one if its argument is true and zero otherwise.

We refer to this as _mOFUL_ : see Algorithm 1. As in (Abbasi-yadkori et al.,
2011), we can obtain the regret bound of the mOFUL algorithm.

######  Theorem 1.

With probability at least $1-\delta$, Algorithm 1 achieves the regret
$R_{T}\leq\mathcal{O}(\sqrt{KT})$, where $K$ is the number of all actions.

Algorithm 1 mOFUL algorithm

Input:

1: for $t=1$ to $T$ do

2: receive context $x_{t}$

3:
$a_{t},\tilde{\theta}_{t,a_{t}}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in
C_{t-1,a}}\langle x_{t},\theta_{a}\rangle$

4: play action $a_{t}$ and receive $r_{t}$

5: update $C_{t,a}$ by Eq(2)

6:

7:

8: end for

Algorithm 2 $\epsilon$-mOFUL algorithm

Input: the offline dataset $S$; the set $\mathcal{L}$

1: for $t=1$ to $T$ do

2: receive context $x_{t}$

3:
$a_{t},\tilde{\theta}_{t,a_{t}}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in
C_{t-1,a}}\langle x_{t},\theta_{a}\rangle$

4: if $a_{t}\in\mathcal{A}\setminus\mathcal{L}$ then

5: play action $a_{t}$ and receive $r_{t}$

6: update $C_{t,a}$ by Eq(3)

7: end if

8: end for

###  4.2 $\epsilon$-mOFUL Algorithm

A natural approach to improve Algorithm 1 is to use the offline data with an
expectation to reduce both the number of reward calls (online explorations)
and the regret. We base this method on using the learned model parameters of
several actions for whom we have "enough" offline data from the logging policy
$\mu$. We assume that there is a subset $\mathcal{L}$ of actions, such that
there are $\epsilon>0$ and $\delta>0$ such that
$|\hat{\theta}_{a}-\theta^{*}_{a}|\leq\epsilon$ holds w.p. at least $1-\delta$
jointly over all $a\in\mathcal{L}$, where $\hat{\theta}_{a}$ denotes the
learned model parameter of action $a$. We call this set of actions
$\epsilon$-_supported actions_.

Unlike the fully online mOFUL algorithm, we here uses only online explorations
to learn reward parameters of the remaining actions, i.e.,
$\mathcal{A}\setminus\mathcal{L}$. The update of confidence interval $C_{t,a}$
now is as follows:

$C_{t,a}=\begin{cases}\\{\hat{\theta}_{a}\\},&\text{if $a\in\mathcal{L}$},\\\
\\{\theta\in\mathbb{R}^{d}:||\hat{\theta}_{t,a}-\theta||_{\overline{V}_{t,a}}\leq\beta_{t}(\delta)\\},&\text{if
otherwise},\end{cases}$ (3)

where $\hat{\theta}_{a}$ is the learned reward for $a\in\mathcal{L}$ as
defined above, $\hat{\theta}_{t,a}$ is defined as in Eq(1);
$\overline{V}_{t,a}=\lambda
I+\sum_{i=1}^{t}x_{i}x_{i}^{T}\mathbf{1}(a_{i}=a)$,
$\sqrt{\beta_{t}(\delta)}=\sigma\sqrt{d\text{log}(\frac{(K-L)(1+tS^{2}_{x}/\lambda)}{\delta})}+\lambda^{1/2}S_{\theta}$;
$S_{x},S_{\theta}$ are upper bounds of $||x||$ and $||\theta^{*}_{a}||$. We
can see that for action $a\in\mathcal{L}$, the confidence interval $C_{t,a}$
contains a unique value which is the learned reward from offline data, and
does not change over time $t$. This allows to reduce the computation in
optimization step at line 4 in each iteration.

We refer to this as _$\epsilon$ -mOFUL_ and describe in Algorithm 2. We next
provide a cumulative regret bound for Algorithm 2.

######  Theorem 2.

Assume that $||x||\leq S_{x}$. With probability at least $1-\delta$, the
$\epsilon$-mOFUL algorithm achieves a regret

$R_{T}\leq\mathcal{O}(\epsilon S_{x}(T-T^{\prime})+\sqrt{(K-L)T^{\prime}}),$

where $T^{\prime}=|\\{1\leq t\leq
T:a_{t}\in\mathcal{A}\setminus\mathcal{L}\\}|$ and $L=|\mathcal{L}|$.

##### Remark 1.

In Theorem 2, $T^{\prime}$ denotes the number of reward calls up to $T$
iterations of the Algorithm 2. $T-T^{\prime}$ is therefore the number of
rewards calls that were saved due to the offline dataset. For each reward call
saving, the first term in the regret bound still incurs a regret that is
linear to $\epsilon$. Therefore, the smaller the $\epsilon$, the smaller is
the first term. The second term in the regret bound is the regret due to
online reward calls and grows only sublinearly with $T^{\prime}\leq T$. The
larger the set of $\epsilon$-supported actions, the smaller is this regret
term.

##### Remark 2.

Some offline model-based learning methods e.g., tensor decomposition
(Anandkumar et al., 2014; Hong et al., 2020) allow for $\epsilon,\delta$ to be
arbitrarily small as the size of offline dataset increases. More simply, under
linear reward models, we also estimate directly the reward parameters of
actions in $\mathcal{L}$ as
$\hat{\theta}_{a}=(\frac{1}{N_{a}}\sum_{i=1}^{N_{a}}x^{\mu}_{i}(x^{\mu}_{i})^{T})^{-1}(\frac{1}{N_{a}}\sum_{i=1}^{N_{a}}x^{\mu}_{i}r^{\mu}_{i})$,
where $N_{a}=\sum_{i=1}^{n}\mathbf{1}(a^{\mu}_{i}=a)$ is the number of data
supporting action $a$ from dataset $S$. Using the assumption that contexts
$\\{x^{\mu}_{i}\\}_{i=1}^{n}$ of $S$ are i.i.d samples from a distribution
$P_{x}$, we can obtain the following proposition:

######  Proposition 2.

For an action $a\in\mathcal{A}$. The following result holds almost surely,

$\text{lim}_{N_{a}\rightarrow\infty}(\frac{1}{N_{a}}\sum_{i=1}^{N_{a}}x^{\mu}_{i}(x^{\mu}_{i})^{T})^{-1}(\frac{1}{N_{a}}\sum_{i=1}^{N_{a}}x^{\mu}_{i}r^{\mu}_{i})=\theta^{*}_{a}.$

If we choose
$\epsilon=\text{max}_{a\in\mathcal{L}}|\hat{\theta_{a}}-\theta^{*}_{a}|$ the
Proposition 2 implies that as $N_{a}$ (the size of $\mathcal{L}$) increases,
$\epsilon$ can be arbitrarily small.

If $T-T^{\prime}\leq\mathcal{O}(1/(S_{x}^{2}\epsilon^{2}))$, the first term of
the upper bound is dominated by the second term. Thus,
$R_{T}=\mathcal{O}(\sqrt{(K-L)T^{\prime}})\leq\mathcal{O}(\sqrt{KT})$. In this
case, Algorithm 2 improves Algorithm 1 in the three aspects: online
explorations, the regret, and the computation at optimization steps. In
extreme cases, when $L=0$, algorithm 2 degenerates to algorithm 1 and when
$L=K$ which implies that the condition at line 5 is unsatisfied for every $t$
and thus no reward call is needed. In this case, if
$T-T^{\prime}\leq\mathcal{O}(1/(S_{x}^{2}\epsilon^{2}))$, the regret of
algorithm 2 is $R_{T}=\mathcal{O}(\sqrt{T}/S_{x})$ which is sublinear in $T$.

##### Remark 3.

In practice, the set $\mathcal{L}$ may be built by for example choosing $L$
actions with the maximum values of
$N_{a}=\sum_{i=1}^{n}\mathbf{1}(a^{\mu}_{i}=a)$ which is the number of data
supporting action $a$ from dataset $S$. Then $\epsilon$ is determined as
$\epsilon=\text{max}_{a\in\mathcal{L}}|\hat{\theta}_{a}-\theta^{*}_{a}|$. By
this way, we can guarantee that all actions in $\mathcal{L}$ are
$\epsilon$-supported actions. We note that $\epsilon$ is not required to be
known for Algorithm 2, but only participates in the upper bound of $R_{T}$ of
Algorithm 2. The value of $L$ can be selected based on the histogram of
actions from $S$ showing $N_{a}$ for each action $a$. If plotted in descending
order, $L$ is the value at which $N_{a}$ starts to diminish fast.

###  4.3 $\epsilon$-mOFUL-IPS Algorithm

Algorithm 2 makes use of availability of the $\epsilon$-supported actions to
reduce the online explorations. In this section, we propose another new policy
learning algorithm which can obtain further reduce online explorations while
keeping a sublinear regret even without the existence of such
$\epsilon$-supported actions. This algorithm exploits "good" context-action
pairs from the offline dataset S.

We consider event $(x^{\mu}_{i},a^{\mu}_{i},r^{\mu}_{i})$ in the offline
dataset $S$. For a context $x^{\mu}_{i}$, a good learning algorithm should
suggest some action $a$ such that the returned reward is at least
$r^{\mu}_{i}$, else this learnt policy is worse than the logging policy. This
observation suggests that if the estimated rewards for all actions by an
algorithm is less than $r^{\mu}_{i}$, then the algorithm should use the action
$a^{\mu}_{i}$ and $r^{\mu}_{i}$ of the logging policy $\mu$, instead of
wasting a reward call.

Further, instead of comparing the estimated rewards for all actions against
$r^{\mu}_{i}$ of $\mu$, we can compare them with a value higher than
$r^{\mu}_{i}$ to further reduce the number of unnecessary reward calls. This
value is the estimated reward of a policy $\mu^{+}$, which is computed as
$r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$,
and the policy $\mu^{+}$ is taken as an optimal policy in the restricted space
$\Pi^{+}\subseteq\Pi$ containing a set of policies
$\pi:\mathcal{X}\rightarrow\mathcal{A}$ where

$\pi(a|x)=\begin{cases}0,&\text{if $a\in\mathcal{U}(x,\mu)$},\\\ >0,&\text{if
otherwise},\end{cases}$

and $M$ is clipping constant of the off policy clipped IPS estimator (Strehl
et al., 2010; Swaminathan and Joachims, 2015b) which is defined as:

$\hat{R}^{M}(\pi)=\frac{1}{|S|}\sum_{i=1}^{|S|}r^{\mu}_{i}\text{min}\\{\frac{\pi(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}.$

The policy space $\Pi^{+}$ contains a class of policies close to logging
policy $\mu$ in the sense that they share the same supported actions (also
same unsupported actions) as $\mu$. Thus, policies in $\Pi^{+}$ have full
support from $\mu$ and it implies that we can find an optimal policy in
$\Pi^{+}$ by using the clipped IPS estimator without online explorations:
$\pi^{+}=\text{argmax}_{\pi\in\Pi^{+}}\hat{R}^{M}(\pi)$. We refer to this
algorithm as _$\epsilon$ -mOFUL-IPS_ and describe it in Algorithm 3. The
comparison of estimated rewards by the algorithm and the estimated reward of
the policy $\pi^{+}$ is performed at line 6. If contexts $x\not\in S$, the
algorithm is similar to Algorithm 2 with confidence intervals updated by
Eq(3). Following the above observations, to make use of contexts in $S$. If
$|S|\geq T$, we use any $T$ contexts from $S$ as contexts of 3. Otherwise, we
use all $|S|$ contexts in $S$ and $T-|S|$ contexts are sampled randomly from
$P_{x}$.

Algorithm 3 $\epsilon$-mOFUL-IPS algorithm

Input: offline dataset S, the set $\mathcal{L}$ of $\epsilon$-supported
actions

1: for $t=1$ to $T$ do

2: receive context $x_{t}$

3:
$a_{t},\tilde{\theta}_{t,a_{t}}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in
C_{t-1,a}}\langle x_{t},\theta_{a}\rangle$

4: if $x_{t}\in S$ and assume $x_{t}$ corresponding to some
$(x^{\mu}_{i},a^{\mu}_{i},r^{\mu}_{i})$ of $S$ then

5: if $\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle>r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$
and $a_{t}\in\mathcal{A}\setminus\mathcal{L}$ then

6: play action $a_{t}$ and receive $r_{t}$

7: update $C_{t,a}$ by Eq(3)

8: end if

9: else

10: if $a_{t}\in\mathcal{A}\setminus\mathcal{L}$ then

11: play action $a_{t}$ and receive $r_{t}$

12: update $C_{t,a}$ by Eq(3)

13: end if

14: end if

15: end for

We next provide a theoretical analysis for Algorithm 3. Given logged dataset
$S$ with size $n$, we define

$u_{\pi}^{i}=r^{\mu}_{i}\text{min}\\{M,\frac{\pi(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})}\\},\text{
}\overline{u}_{\pi}=\frac{1}{n}\sum_{i=1}^{n}u^{i}_{\pi}\text{ ,
}Var(\pi)=\sum_{i=1}^{n}(u^{i}_{\pi}-\overline{u}_{h})^{2}/(n-1),$

and a reward function class
$\mathcal{F}_{\Pi}=\\{f_{\pi}:\mathcal{X}\times\mathcal{A}\rightarrow[0,1]\\}$.
The covering number $N(1/n,\mathcal{F}_{\Pi},2n)$ is the size of the smallest
cardinality subset $A_{0}\in\mathcal{F}_{\Pi}$ such that $\mathcal{F}_{\Pi}$
is contained in the union of balls of radius $1/n$. We get the following upper
bound for $R_{T}$.

######  Theorem 3.

Assume that $||x||\leq S_{x}$. For any $\epsilon\geq 0$ and $T>0$, with
probability at least $1-\delta$, the $\epsilon$-mOFUL-IPS algorithm achieves
an upper bound on the regret

$R_{T}\leq\mathcal{O}(\epsilon
S_{x}(T-T^{\prime}-T^{\prime\prime})+\sqrt{(K-L)T^{\prime}}+\sqrt{Var(\pi^{+})log(N(1/T^{\prime\prime},\mathcal{F}_{\Pi},2T^{\prime\prime})/\delta)T^{\prime\prime}}),$

where $T^{\prime}=|\\{1\leq t\leq T:\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle>r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}\text{
and }a_{t}\in\mathcal{A}\setminus\mathcal{L}\\}|$; $T^{\prime\prime}=|\\{1\leq
t\leq T:\langle x_{t},\tilde{\theta}_{t,a_{t}}\rangle\leq
r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}\\}|$;
$Var(\pi^{+})$ and $N(1/T,\mathcal{F}_{\Pi},2T)$ are defined as above;

##### Remark 4.

Following (Zhou et al., 2018),
$\sqrt{Var(\pi^{+})log(N(1/T,\mathcal{F}_{\Pi},2T)/\delta)T})$ is sublinear in
$T$. If
$T-T^{\prime}-T^{\prime\prime}\leq\mathcal{O}(1/(S_{X}^{2}\epsilon^{2}))$, the
first term of Theorem 3 is dominated, hence the regret of the
$\epsilon$-mOFUL-IPS algorithm achieves a sublinear rate in $T$. In Theorem 3,
$T^{\prime}$ denotes the number of reward calls up to $T$ iterations of the
Algorithm 3. Compared to the number of reward calls of the Algorithm 2, the
Algorithm 3’s one is potentially smaller.

##### Remark 5.

If $L=0$ i.e., there is no availability of $\epsilon$-supported actions, then
$T=T^{\prime}+T^{\prime\prime}$ which implies that the first term is removed.
The algorithm still guarantees a sublinear rate.

##  5 Experiments

(a) $n^{UA}=0.2$, $L=5$ (b) $n^{UA}=0.2$, $L=10$ (c) $n^{UA}=0.2$, $L=12$

Figure 1: The results for a fixed number of average unsupported action
$n^{UA}$ and varying number of supported actions L. Our proposed offline-
online methods are better than fully online method and the reward call saving
increases with increasing $L$.

We empirically compare the performance of our two algorithms $\epsilon$-mOFUL
and $\epsilon$-mOFUL-IPS to two baselines: (1) the fully online learning
algorithm, mOFUL, as described in Algorithm 1; (2) the fully offline learning
algorithm based on policy restriction in (Sachdeva et al., 2020), denoted by
OPR.

##### Support Deficiency Setting

Let $n^{UA}=\mathbb{E}_{x\in\mathcal{X}}[\frac{|\mathcal{U}(x,\mu)|}{K}]$ be
the average number of unsupported actions of logging policy $\mu$ given a set
of context $\mathcal{X}$ and a set of actions $\mathcal{A}=\\{1,2,..,K\\}$. To
create a logging policy $\mu$ at some level, for example $n^{UA}=0.5$, we do
the following: for each $x$, we randomly select a set of $50\%$ of actions in
$\mathcal{A}$. We consider this set as $\mathcal{U}(x,\mu)$, and create the
logged data by considering the actions in the complement of this set. To build
a data set from the logging policy $\mu$, for each $x$, we select uniformly at
random an action $a\in\mathcal{U}^{c}(x,\mu)$ which is in the set of supported
actions for $x$. In this manner, for each $a\in\mathcal{U}(x,\mu)$:
$\mu(a|x)=0$ and for each $a\in\mathcal{U}^{c}(x,\mu)$:
$\mu(a|x)=\frac{2}{K}$.

###  5.1 Synthetic Experiments

Figure 2: The average reward of different learning algorithms vs. $\%$ of
unsupported actions, $n^{UA}$ for logging policy $\mu$. We performed
experiments for $n^{UA}=[0,0.2,0.4,0.6,0.8]$.

We first experiment with synthetic contextual bandits with $|\mathcal{A}|=20$.
We use a linear reward model: $r(x,a)=\langle x,\theta^{*}_{a}\rangle+\eta$,
where $\theta^{*}_{a}$ is the parameter for action $a$, drawn i.i.d from
$\mathcal{N}(0,1)$, and $\eta$ is the noise, drawn i.i.d from
$\mathcal{N}(0,\sigma^{2})$, where $\sigma=2$. The contexts $x$ are sampled
uniformly at random in $[0,1]$. For $\epsilon$-mOFUL and $\epsilon$-mOFUL-IPS,
we let $\epsilon=0.05$. To build the set $\mathcal{L}$ of $\epsilon$-supported
actions, we choose a set of any $L$ actions and sample $\hat{\theta}_{a}$ from
$\mathcal{N}(\theta^{*}_{a},\epsilon^{2})$ for each action in $\mathcal{L}$.

We create a dataset for logging policy $\mu$ which is large enough to support
each action in $\mathcal{L}$. OPR is learnt using a direct loss minimization
(DLM) algorithm of Hazan et al. (2010) as in (Dudík et al., 2011). For our
proposed $\epsilon$-mOFUL-IPS, we learn $\pi^{+}$ via the linear programming
(LP): $\text{max}_{\pi\in\Pi}\sum_{(x,a,r)\in
S}r_{i}\frac{\pi(a|x)}{\mu(a|x)}\text{ subject to
}0\leq\frac{\pi(a|x)}{\mu(a|x)}\leq M,$ where the clipping constant $M$ is set
to the ratio of the $90$-th percentile to the $10$-th percentile propensity
score observed in the training set.

The efficiency of our proposed algorithms is measured via (1) the number of
reward function calls, and (2) the estimated average reward. Lower the number
of reward function calls, and higher the value of estimated average reward,
the greater the efficiency of the algorithm is.

####  5.1.1 On the number of online reward function calls

We test the influence of $L$ and $n^{UA}$ on the number of reward function
calls.

##### On the influence of $L$ parameter:

We fix $n^{UA}=0.2$ and consider three different values of $L$: $L=5,L=10$ and
$L=12$. As shown in Section 5, all these algorithms converge sub-linearly.
However, while mOFUL needs to use one reward call at each iteration, our
algorithms uses fewer reward calls as $L$ increases. This is presented in
Figure 1. Proposed $\epsilon$-mOFUL-IPS algorithm uses the least number of
reward calls because it only makes a reward call if the chosen action does not
belong to $\mathcal{L}$ and satisfies the condition at Line 6 in Algorithm 3.
In particular, when $L=12$, the number of reward calls is only about $20\%$ of
mOFUL’s calls.

##### On the influence of $n^{UA}$ parameter:

We provide results in Supplementary Material.

####  5.1.2 On the efficiency of the algorithms

We now fix the number of reward calls and compare the algorithms using the
estimated average reward. Each algorithm provides a learnt policy. Given
contexts $\\{x_{1},x_{2},...,x_{T}\\}$ and a policy $\pi$, for the algorithms
using online explorations, we compute the average reward as
$\sum_{i=1}^{T}\frac{1}{T}\langle x_{i},\theta^{*}_{\pi(x_{i})}\rangle$. For
OPR, since the policy $\pi$ is stochastic, the average reward is computed as
$\sum_{i=1}^{T}\frac{1}{T}\langle x_{i},\theta^{*}_{\pi(a|x_{i})}\rangle$,
where action $a$ is chosen randomly from $\mathcal{U}(x_{i},\pi)$. We compared
estimated rewards of the algorithms with different values of
$n^{UA}=0;0.2;0.4;0.6;0.8$. We allow $T$ increasing but fix $L=300$ across all
values of $n^{UA}$. The result is shown in Figure 2. The estimated reward of
OPR is the worst across all $n^{UA}$. This is because OPR only searches
optimal policies in a restricted subspace closed to the logging policy $\mu$,
does not use online exploration, and thus fails to find optimal policies. The
performance is worse for higher the level of unsupported actions. In contrast,
mOFUL, $\epsilon$-mOFUL and $\epsilon$-mOFUL-IPS can find optimal policies for
all the levels of unsupported actions. mOFUL does not use offline data, the
estimated rewards are nearly the same for all the levels of unsupported
actions. $\epsilon$-mOFUL and $\epsilon$-mOFUL-IPS leverage a large amount of
offline data to learn reward model and thus, are more efficient than mOFUL.
$\epsilon$-mOFUL-IPS leverages both learnt reward model and an optimal policy
$\pi^{+}$ of the subset of policy space generated from the supported actions
of $\mu$, and runs well especially for small levels of unsupported actions. In
summary, our proposed $\epsilon$-mOFUL and especially $\epsilon$-mOFUL-IPS
achieves better efficiency than mOFUL given the same reward calls.

###  5.2 Multi-class Classification with Bandit Feedback

(a) letter dataset (b) pendigits dataset (c) satimage dataset

Figure 3: Classification error for different algorithms as average number of
the unsupported actions increases ($n^{UA}=[0,0.2,0.4,0.6,0.8]$). Table 1:
Characteristics of benchmark datasets used in Section 5.2.

Dataset | letter | pendigits | satimage
---|---|---|---
Classes ($K$) | 26 | 10 | 6
Dataset size | 20000 | 10992 | 6435

Next, we learn optimal policies for classification tasks using the three UCI
datasets previously considered for offline-policy learning in Dudík et al.
(2011). The datasets are described in Table 1. We assume that data are drawn
from a fixed distribution: $(x,c)\sim D$, where $x\in\mathcal{X}$ is a feature
vector and $c\in\\{1,2,..,K\\}$ is the class label. A typical goal is to find
a classifier $\pi:\mathcal{X}\rightarrow\\{1,2,..,K\\}$ minimizing the
classification error: $e(\pi)=\mathbb{E}_{(x,a)\sim
D}[\textbf{1}(\pi(x)\not=c)]$.

We convert the multi-class classification problem to contextual bandits by
treating the labels as actions for a policy $\mu$, and recording the reward of
1 if the correct label is chosen, and 0 otherwise. We turn a data point
$(x,c)$ into a classification example $(x,r_{1},r_{2},...,r_{K})$, where
$r_{a}=\textbf{1}(a\not=c)$ is the loss (reward) for predicting $a$. We note
that only $r_{a}$ is revealed. In addition to this noiseless reward model, we
also consider a noisy reward model for each data set, which reveals the
correct reward with probability 0.5 and outputs a random coin toss otherwise.
We use a linear loss model $r(x,a)=\langle x,\theta^{*}_{a}\rangle+\eta$,
where $\theta^{*}_{a}$ is the unknown parameter of action $a$, and $\eta$ is
the noise defined as above. We randomly split data into two sets, one ($70\%$)
set to build the logging policy and ($30\%$) set to build algorithms requiring
online explorations. The logging policy with different levels of unsupported
actions as well as the algorithms are implemented as for the synthetic
function except that contexts $x$ are obtained from datasets and the
parameters $\theta_{a}^{*}$ of actions are assumed to be unknown. The set of
$\epsilon$-supported actions is built as Remark 3 mentioned. We show this in
Supplementary Material.

We test the performance of the algorithms in terms of the classification error
for all three datasets. The results are shown in Figure 3. Similar to the
synthetic experiments, our $\epsilon$-mOFUL-IPS algorithm achieves the best
performance as its classification error is the lowest among all algorithms
consistently on all datasets. OPR is the worst among all algorithms on all
datasets. It is because OPR only searches optimal policies in a restricted
subspace close to the logging policy $\mu$. This algorithm does not use online
explorations and thus fails to find policies that are optimal in the whole
policy space. The performance of $\epsilon$-mOFUL and mOFUL are nearly similar
because the amount of data is not enough to learn the $\epsilon$-supported
actions as well as in the synthetic experiments.

##  6 Conclusion

We study the problem of policy learning with logged data in contextual bandits
with deficient support. Due to the deficient support, the policies learnt in
the offline setting are biased. To solve this problem, we combine the offline-
policy learning with online explorations. We propose two algorithms. The first
algorithm leverages reward models learned from offline data to reduce the
number of online explorations. The second algorithm further improves the
efficiency of the first algorithm to reduce the number of online interactions
by exploiting good context-action pairs in offline data. We perform
experiments with both synthetic and real datasets and show the efficiency of
our algorithms.

## References

  * Abbasi-yadkori et al. [2011] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 24, pages 2312–2320. Curran Associates, Inc., 2011.
  * Agarwal et al. [2014] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire.  Taming the monster: A fast and simple algorithm for contextual bandits.  In Eric P. Xing and Tony Jebara, editors, _Proceedings of the 31st International Conference on Machine Learning_ , volume 32 of _Proceedings of Machine Learning Research_ , pages 1638–1646, Bejing, China, 22–24 Jun 2014. PMLR.
  * Agrawal and Goyal [2013] Shipra Agrawal and Navin Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In Sanjoy Dasgupta and David McAllester, editors, _Proceedings of the 30th International Conference on Machine Learning_ , volume 28 of _Proceedings of Machine Learning Research_ , pages 127–135, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * Anandkumar et al. [2014] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky.  Tensor decompositions for learning latent variable models.  _Journal of Machine Learning Research_ , 15(80):2773–2832, 2014.  URL http://jmlr.org/papers/v15/anandkumar14b.html.
  * Chu et al. [2011] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , volume 15 of _Proceedings of Machine Learning Research_ , pages 208–214, Fort Lauderdale, FL, USA, 11–13 Apr 2011\. JMLR Workshop and Conference Proceedings.
  * Dudík et al. [2011] Miroslav Dudík, John Langford, and Lihong Li.  Doubly robust policy evaluation and learning.  ICML’11, page 1097–1104, Madison, WI, USA, 2011. Omnipress.  ISBN 9781450306195.
  * Farajtabar et al. [2018] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh.  More robust doubly robust off-policy evaluation.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1447–1456, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * Hazan et al. [2010] Tamir Hazan, Joseph Keshet, and David McAllester.  Direct loss minimization for structured prediction.  In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, _Advances in Neural Information Processing Systems_ , volume 23, pages 1594–1602. Curran Associates, Inc., 2010.  URL https://proceedings.neurips.cc/paper/2010/file/ca8155f4d27f205953f9d3d7974bdd70-Paper.pdf.
  * Hong et al. [2020] Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed, and Craig Boutilier.  Latent bandits revisited.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 13423–13433. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/9b7c8d13e4b2f08895fb7bcead930b46-Paper.pdf.
  * Horvitz and Thompson [1952] D. G. Horvitz and D. J. Thompson.  A generalization of sampling without replacement from a finite universe.  _Journal of the American Statistical Association_ , 47(260):663–685, 1952.  ISSN 01621459.  URL http://www.jstor.org/stable/2280784.
  * Jin et al. [2020] Ying Jin, Zhuoran Yang, and Zhaoran Wang.  Is pessimism provably efficient for offline rl?, 2020.
  * Kato et al. [2020] Masahiro Kato, Masatoshi Uehara, and Shota Yasui.  Off-policy evaluation and learning for external validity under a covariate shift, 2020.
  * Levine et al. [2020] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems, 2020.
  * Li et al. [2010] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th International Conference on World Wide Web_ , WWW ’10, page 661–670, New York, NY, USA, 2010. Association for Computing Machinery.  ISBN 9781605587998.  doi: 10.1145/1772690.1772758.  URL https://doi.org/10.1145/1772690.1772758.
  * Liu et al. [2020] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill.  Provably good batch off-policy reinforcement learning without great exploration.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Sachdeva et al. [2020] Noveen Sachdeva, Yi Su, and Thorsten Joachims.  Off-policy bandits with deficient support.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’20, page 965–975, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450379984.
  * Shivaswamy and Joachims [2012] Pannagadatta Shivaswamy and Thorsten Joachims.  Multi-armed bandit problems with history.  In Neil D. Lawrence and Mark Girolami, editors, _Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics_ , volume 22 of _Proceedings of Machine Learning Research_ , pages 1046–1054, La Palma, Canary Islands, 21–23 Apr 2012. PMLR.  URL http://proceedings.mlr.press/v22/shivaswamy12.html.
  * Strehl et al. [2010] Alex Strehl, John Langford, Lihong Li, and Sham M Kakade.  Learning from logged implicit exploration data.  In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, _Advances in Neural Information Processing Systems_ , volume 23, pages 2217–2225. Curran Associates, Inc., 2010.  URL https://proceedings.neurips.cc/paper/2010/file/c0f168ce8900fa56e57789e2a2f2c9d0-Paper.pdf.
  * Su et al. [2019] Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims.  CAB: Continuous adaptive blending for policy evaluation and learning.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 6005–6014. PMLR, 09–15 Jun 2019.
  * Swaminathan and Joachims [2015a] Adith Swaminathan and Thorsten Joachims.  The self-normalized estimator for counterfactual learning.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28, pages 3231–3239. Curran Associates, Inc., 2015a.  URL https://proceedings.neurips.cc/paper/2015/file/39027dfad5138c9ca0c474d71db915c3-Paper.pdf.
  * Swaminathan and Joachims [2015b] Adith Swaminathan and Thorsten Joachims.  Batch learning from logged bandit feedback through counterfactual risk minimization.  _Journal of Machine Learning Research_ , 16(52):1731–1755, 2015b.
  * Swaminathan et al. [2017] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudík, John Langford, Damien Jose, and Imed Zitouni.  Off-policy evaluation for slate recommendation.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 3635–3645, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Tennenholtz et al. [2020] Guy Tennenholtz, Uri Shalit, Shie Mannor, and Yonathan Efroni.  Bandits with partially observable offline data, 2020.
  * Wang et al. [2017] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík.  Optimal and adaptive off-policy evaluation in contextual bandits.  In _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17, page 3589–3597. JMLR.org, 2017.
  * Xie et al. [2019] Yuan Xie, Boyi Liu, Qiang Liu, Zhaoran Wang, Yuan Zhou, and Jian Peng.  Off-policy evaluation and learning from logged bandit feedback: Error reduction via surrogate policy.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_ , 2019.  URL https://openreview.net/forum?id=HklKui0ct7.
  * Ye et al. [2020] Li Ye, Yishi Lin, Hong Xie, and John C. S. Lui.  Combining offline causal inference and online bandit learning for data driven decisions.  _CoRR_ , abs/2001.05699, 2020.
  * Zhou and Brunskill [2016] Li Zhou and Emma Brunskill.  Latent contextual bandits and their application to personalized recommendations for new users.  In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence_ , IJCAI’16, page 3646–3653. AAAI Press, 2016.  ISBN 9781577357704.
  * Zhou et al. [2018] Zhengyuan Zhou, Susan Athey, and Stefan Wager.  Offline multi-action policy learning: Generalization and optimization, 2018.

Supplementary Material

##  Appendix A Additional Experiments

##### On the influence of $n^{UA}$ parameter

We fix $L=4$. We vary the average number of unsupported actions, $n^{UA}$ as
$n^{UA}=0.2,n^{UA}=0.4$ and $n^{UA}=0.6$. As shown in Figure 4, mOFUL always
requires one reward call at each iteration. The efficiency of $\epsilon$-mOFUL
does not change across the different values of $n^{UA}$ as the set of
$\epsilon$\- supported actions and the learnt parameter $\theta^{+}_{a}$ are
fixed. As expected, when $n^{UA}$ decreases, the number of supported actions
increases, therefore $\epsilon$-mOFUL-IPS requires fewer reward calls due to
learnt policy $\pi^{+}$.

(a) $n^{UA}=0.6$, $L=4$ (b) $n^{UA}=0.4$, $L=4$ (c) $n^{UA}=0.2$, $L=4$

Figure 4: A fixed $L$ and varying number of average unsupported actions
$n^{UA}$. As $n^{UA}$ decreases, our proposed offline-online methods
increasingly save the number of reward calls.

##  Appendix B Proof of Theorem 1

In this section, we provide a proof for Theorem 1. The proof technique is
standard and similar to the one of [Abbasi-yadkori et al., 2011].

By adapting the proofs of [Abbasi-yadkori et al., 2011], we achieve the
following results under our model.

######  Lemma 1 (Based on Theorem 2 of [Abbasi-yadkori et al., 2011]).

Let $V=I\lambda$, $\lambda>0$ and assume that $||\theta^{*}_{a}||\leq
S_{\theta}$ and $||x||\leq S_{x}$ for every $a\in\mathcal{A}$ and every $x\in
mathcalX$. Then for any $\delta\in(0,1)$, with probability at least
$1-\delta$, for all $a$ and $t$, $\theta^{*}_{a}$ lies in the set

$C_{t,a}=\\{\theta\in\mathbb{R}:||\hat{\theta}_{t,a}-\theta||_{\overline{V}_{t,a}}\leq\beta_{t}\\},$

where $\overline{V}_{t,a}=\lambda
I+\sum_{i=1}^{t}x_{i}x_{i}^{T}\mathbf{1}(a_{i}=a)$ and
$\sqrt{\beta_{t}(\delta)}=\sigma\sqrt{dlog(\frac{K-(1+tS^{2}_{x}/\lambda)}{\delta})}+\lambda^{1/2}S_{\theta}$.

######  Lemma 2 (Based on Lemma 11 of [Abbasi-yadkori et al., 2011]).

Let $\\{x_{t}\\}_{t=1}^{\infty}$ be a sequence in $\mathbb{R}^{d}$ and
$V_{t}=V+\sum_{i=1}^{t}x_{i}x_{i}^{T}$. Assume that $||x_{t}||\leq S_{x}$ for
all $t$. Then

$\sum_{i=1}^{t}\text{min}(||x_{i}||^{2}_{V^{-1}_{i-1}},1)\leq
2log(\frac{det(V_{t})}{det(V)})\leq
2dlog(\frac{trace(V)+tS_{x}^{2}}{d})-2log(det(V)).$

Following the technique of [Abbasi-yadkori et al., 2011], we first analyze the
regret $r_{t}=\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ at each iteration $t$ as follows.

$\displaystyle r_{t}$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle x_{t},\theta^{*}_{a_{t}}\rangle$
$\displaystyle\leq$ $\displaystyle\langle
x_{t},\tilde{\theta}_{t,a_{t}}-\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$
$\displaystyle\langle
x_{t},\tilde{\theta}_{t,a_{t}}-\hat{\theta}_{t-1,a_{t}}\rangle+\langle
x_{t},\hat{\theta}_{t-1,a_{t}}-\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$
$\displaystyle||x_{t}||_{\overline{V}^{-1}_{t-1,a_{t}}}||\tilde{\theta}_{t,a_{t}}-\hat{\theta}_{t-1,a_{t}}||_{\overline{V}^{-1}_{t-1,a_{t}}}+||x_{t}||_{\overline{V}^{-1}_{t-1,a_{t}}}||\hat{\theta}_{t-1,a_{t}}-\theta^{*}_{a_{t}}||_{\overline{V}^{-1}_{t-1,a_{t}}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a_{t}}}.$

Next, notice that $r_{t}\leq 2$. Given a $a\in\mathcal{A}$, we denote
$N_{t}(a)=|\sum_{i=1}^{t}\textbf{1}\\{a_{i}=a\\}|$. We can upper bound the
cumulative regret $R_{T}=\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ after $T$ iterations as follows:

$\displaystyle R_{T}$ $\displaystyle\leq$
$\displaystyle\sqrt{T\sum_{t=1}^{T}r^{2}_{t}}$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}r_{t}$ $\displaystyle\leq$ $\displaystyle
2\sqrt{T\sum_{t=1}^{T}\beta_{t-1}(\delta)\text{min}\\{||x_{t}||_{\overline{V}^{-1}_{t-1,a_{t}}},1\\}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{T\beta_{T}(\delta)\sum_{a\in\mathcal{A}}\sum_{i=1}^{N_{T}(a)}\text{min}\\{||x_{I_{i}(a)}||_{\overline{V}^{-1}_{I_{i}(a),a}},1\\}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{T\beta_{T}(\delta)}\sqrt{d\sum_{a\in\mathcal{A}}log(\lambda+\frac{N_{T}(a)S^{2}_{x}}{d})}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{T\beta_{T}(\delta)}\sqrt{dKlog(\lambda+\frac{TS^{2}_{x}}{dK})}$
$\displaystyle=$ $\displaystyle\mathcal{O}(\sqrt{KT}),$

where in the forth inequality, we use Lemma 3. In the last inequality, we use
Jensen’s inequality and the fact that $\sum_{a\in\mathcal{A}}N_{T}(a)=T$. We
here hide the influence of the number of dimensions $d$. Thus, the theorem is
proven.

##  Appendix C Proof of Proposition 2

######  Proposition 3.

The following result holds almost surely for all $a\in\mathcal{A}$.

$\text{lim}_{N_{a}\rightarrow\infty}(\frac{1}{N_{a}}\sum_{i=1}^{N_{a}}x_{i}x_{i}^{T})^{-1}(\frac{1}{N_{a}}\sum_{i=1}^{N_{a}}x_{i}r_{i})=\theta^{*}_{a},$

where $N_{a}=\sum_{i=1}^{N}\mathbf{1}(a_{i}=a)$, and the $x_{i},r_{i}$
correspond to action $a_{i}$.

###### Proof.

The correctness of the proposition is based on the fact that all the contexts
in the dataset are i.i.d. The proof is similar to that of Proposition 1 in
[Tennenholtz et al., 2020]. The difference is that their model is applied for
confounding bandits in which only $M<d$ features of the context are observed
while all features of the context are observed in our setting. Therefore we
can apply their proof for the case $M=d$. ∎

##  Appendix D Proof of Theorem 2

In this section, we provide the proof for Theorem 2.

###### Proof.

Let the instantaneous regret $r_{t}=\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$. We decompose $R_{T}$ as follows:

$\displaystyle R_{T}$ $\displaystyle=$ $\displaystyle\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}(\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle)$ $\displaystyle=$
$\displaystyle\underbrace{\sum_{i\in S^{(1)}}r_{i}}_{\text{Term
1}}+\underbrace{\sum_{i\in S^{(2)}}r_{i}}_{\text{Term 2}},$

where

$S^{(1)}=\\{1\leq t\leq T|a_{t}\in\mathcal{L}(\mu)\\},$ $S^{(2)}=\\{1\leq
t\leq T|a_{t}\in\mathcal{A}\setminus\mathcal{L}(\mu)\\}.$

Since the sets $S^{(1)},S^{(2)}$ are disjoint, we have that
$|S^{(1)}|+|S^{(2)}|=T$. We let $|S^{(2)}|=T^{\prime}$. To bound $R_{T}$, we
bound Term 1, Term 2 respectively.

##### Bounding Term 1

$\displaystyle\sum_{i\in S^{(1)}}r_{i}$ $\displaystyle=$
$\displaystyle\sum_{i\in S^{(1)}}\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\sum_{i\in
S^{(1)}}\langle x_{t},\hat{\theta}_{a_{t}}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\sum_{i\in
S^{(1)}}\langle x_{t},\hat{\theta}_{a_{t}}-\theta^{\epsilon}_{a_{t}}\rangle$
$\displaystyle\leq$ $\displaystyle\sum_{i\in
S^{(1)}}||x_{t}||||\hat{\theta}_{a_{t}}-\theta^{\epsilon}_{a_{t}}||$
$\displaystyle\leq$ $\displaystyle\sum_{i\in S^{(1)}}\epsilon S_{x}$
$\displaystyle\leq$ $\displaystyle\epsilon S_{x}(T-T^{\prime})$

##### Bounding Term 2

Following the proof steps similar to that of mOFUL, we have that with
probability at least $1-\delta$, $\sum_{i\in
S^{(2)}}r_{i}\leq\mathcal{O}(\sqrt{(K-L)T^{\prime}})$.

$\displaystyle\sum_{t\in S^{(2)}}r_{i}$ $\displaystyle\leq$
$\displaystyle\sqrt{T_{2}\sum_{t\in S^{(2)}}r^{2}_{t}}$ $\displaystyle\leq$
$\displaystyle 2\sqrt{T^{\prime}\sum_{t\in
S^{(2)}}\beta_{t-1}(\delta)\text{min}\\{||x_{t}||_{\overline{V}^{-1}_{t-1,a_{t}}},1\\}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{T^{\prime}\beta_{T}(\delta)\sum_{a\in
S^{(2)}}\sum_{i=1}^{N_{T}(a)}\text{min}\\{||x_{I_{i}(a)}||_{\overline{V}^{-1}_{I_{i}(a),a}},1\\}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{T^{\prime}\beta_{T}(\delta)}\sqrt{d\sum_{a\in
S^{(2)}}log(\lambda+\frac{N_{T}(a)S^{2}_{x}}{d})}$ $\displaystyle\leq$
$\displaystyle
2\sqrt{T^{\prime}\beta_{T}(\delta)}\sqrt{d(K-L)log(\lambda+\frac{TS^{2}_{x}}{d(K-L)})}$
$\displaystyle=$ $\displaystyle\mathcal{O}(\sqrt{(K-L)T^{\prime}}).$

Combining the bounds of Term 1 and Term 2, Theorem 2 holds. ∎

##  Appendix E Proof of Theorem 3

In this section, we will derive a regret for the $\epsilon$-mOFUL-IPS
algorithm. We first start with Lemma 1 which is stated as follows. This lemma
provides a manner to upper bound the gap $R^{+}(\pi)-\hat{R}^{M}(\pi)$.

######  Lemma 3 (Based on Theorem 1 of [Swaminathan and Joachims, 2015b]).

Given $(x_{1},a_{1}),...,(x_{n},a_{n})$ where $x_{i}$ is sampled uniformly at
random in $\mathcal{X}$, $a_{i}\sim\mu(x_{i})$, for $n\geq 16$ and for every
$\pi\in\Pi^{+}$ we have, with probability at least $1-\delta$,

$R^{+}(\pi)\leq\hat{R}^{M}(\pi)+\mathcal{O}(\sqrt{Var_{\pi}log(N(1/n,\mathcal{F}_{\Pi},2n)/\delta)/n}),$

###### Proof.

Given a $\pi\in\Pi^{+}$, by definition we have

$\hat{R}^{M}(\pi)=\frac{1}{|S|}\sum_{(x,a,r)\in
S}r\text{min}\\{\frac{\pi(a|x)}{\mu(a|x)},M\\}.$

In the restricted space $\Pi^{+}$, the logging policy $\mu$ has a full support
for all policy $\pi\in\Pi^{+}$. By the proof similar to the one of Theorem 1
of [Swaminathan and Joachims, 2015b], we can obtain a generalization error
bound for $R^{+}(\pi)-\hat{R}^{M}(\pi)$. ∎

We next provide the regret bound for Theorem 3. We start with the definition
of the regret $R_{T}$:

$R_{T}=\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{a_{t}}\rangle,$

where $a_{t}$ is the action chosen by the algorithm. Following the
$\epsilon$-mOFUL-IPS algorithm, we define $a_{t}$ as follows:

$a_{t}=\begin{cases}\pi^{+}(x_{t}),&\text{if $x_{t}\in S$ and the condition at
line 5 (Algorithm 3) is not satisfied},\\\
\text{argmax}_{a\in\mathcal{A},\theta_{a}\in C_{t-1,a}}\langle
x_{t},\theta_{a}\rangle,&\text{if otherwise}.\end{cases}$

To upper bound $R_{T}$, we will upper bound $r_{t}=\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$, for every $1\leq t\leq T$. We consider the
three cases:

  * •

Case 1: $a_{t}=\pi^{+}(x_{t})$;

  * •

Case 2: $a_{t}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in C_{t-1,a}}\langle
x_{t},\theta_{a}\rangle$ and $a_{t}\in\mathcal{A}\setminus\mathcal{L}$;

  * •

Case 3: $a_{t}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in C_{t-1,a}}\langle
x_{t},\theta_{a}\rangle$ and $a_{t}\in\mathcal{L}$.

Case 1: $a_{t}=\pi^{+}(x_{t})$. This holds when the condition at line 5 is not
satisfied, i.e., $\langle x_{t},\tilde{\theta}_{t,a_{t}}\rangle\leq
r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$,
where $(x^{\mu}_{i},a^{\mu}_{i},r^{\mu}_{i})\in S$ such that
$x^{\mu}_{i}=x_{t}$.

We consider the policy $\pi^{*}_{\mu}$ which is defined as
$\pi^{*}_{\mu}(x)\in\text{argmax}_{a\in\mathcal{U}(x,\mu)}\langle
x,\theta^{*}_{a}\rangle$. $\pi^{*}_{\mu}$ is regarded as the optimal policy
for the unsupported actions. By this, we have that $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle\geq\langle
x,\theta^{*}_{\pi^{*}_{\mu}(x)}\rangle$.

Now we consider the following two cases for the relation between
$\pi^{*}(x_{t})$ and $\pi^{*}_{\mu}(x_{t})$:

  * •

if $\pi^{*}(x_{t})=\pi^{*}_{\mu}(x_{t})$ then

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{*}_{\mu}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle$ $\displaystyle\leq$
$\displaystyle\langle x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle$ $\displaystyle\leq$ $\displaystyle
r_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle,$

where the first inequality holds because
$a_{t},\tilde{\theta}_{t,a_{t}}=\text{argmax}_{a\in S_{t},\theta_{a}\in
C_{t-1,a}}\langle x_{t},\theta_{a}\rangle$. The second one holds because of
the assumption of Case 1.

  * •

if $\pi^{*}(x_{t})\not=\pi^{*}_{\mu}(x_{t})$ then $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle>\langle
x,\theta^{*}_{\pi^{*}_{\mu}(x)}\rangle$. Therefore, $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle=\langle x,\theta^{*}_{\pi^{+}(x)}\rangle$,
where policy $\pi^{+}$ is defined in Section 3.3 and it is regarded as the
optimal policy for the supported actions by logging policy $\mu$. Thus,

$\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle=\langle
x,\theta^{*}_{\pi^{+}(x)}\rangle-\langle x,\theta^{*}_{\pi^{+}(x)}\rangle=0.$

Case 2: $a_{t}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in C_{t-1,a}}\langle
x_{t},\theta_{a}\rangle$ and $a_{t}\in\mathcal{A}\setminus\mathcal{L}$. We
continue to consider the two cases: Case (i): $x_{t}\in S$, $\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle>r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$
and $a_{t}\in\mathcal{U}(x_{t},\mu)\setminus\mathcal{L}$, and Case (ii)
$x_{t}\not\in S$ and $a_{t}\in\mathcal{A}\setminus\mathcal{L}$.

  * •

Case (i). For this case, we continue to consider two cases:

    * –

if $\pi^{*}(x_{t})=\pi^{*}_{\mu}(x_{t})$ then

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{*}_{\mu}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle x_{t},\theta^{*}_{a_{t}}\rangle$
$\displaystyle=$ $\displaystyle\langle
x_{t},\tilde{\theta}_{t,a_{t}}-\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$
$\displaystyle\langle
x_{t},\tilde{\theta}_{t,a_{t}}-\hat{\theta}_{t-1,a_{t}}\rangle+\langle
x_{t},\hat{\theta}_{t-1,a_{t}}-\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$
$\displaystyle||x_{t}||_{\overline{V}^{-1}_{t-1,a}}||\tilde{\theta}_{t,a_{t}}-\hat{\theta}_{t-1,a_{t}}||_{\overline{V}^{-1}_{t-1,a}}+||x_{t}||_{\overline{V}^{-1}_{t-1,a}}||\hat{\theta}_{t-1,a_{t}}-\theta^{*}_{a_{t}}||_{\overline{V}^{-1}_{t-1,a}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}}$

    * –

if $\pi^{*}(x_{t})\not=\pi^{*}_{\mu}(x_{t})$ then $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle>\langle
x,\theta^{*}_{\pi^{*}_{\mu}(x)}\rangle$. Therefore, $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle=\langle x,\theta^{*}_{\pi^{+}(x)}\rangle$.

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle+\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle x_{t},\theta^{*}_{a_{t}}\rangle$
$\displaystyle\leq$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}+\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle x_{t},\theta^{*}_{a_{t}}\rangle$
$\displaystyle\leq$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}+2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}},$

where the first inequality, we use the assumption of Case 2 that $\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle>r_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$.
In the last inequality, we use the proof similar as above (when
$\pi^{*}(x_{t})=\pi^{*}_{\mu}(x_{t})$ in Case 2).

  * •

Case (ii). We have

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle
2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}},$

where in the last inequality, we use the proof similar as above. This case is
as in the $\epsilon$-mOFUL without using an offline estimator.

Case 3: $a_{t}=\text{argmax}_{a\in\mathcal{A},\theta_{a}\in C_{t-1,a}}\langle
x_{t},\theta_{a}\rangle$ and $a_{t}\in\mathcal{L}$. Similar to Case 2, we
consider the two cases: Case (i): $x_{t}\in S$, $\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle>r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$
and $a_{t}\in\mathcal{L}(\mu)$, and Case (ii) $x_{t}\not\in S$ and
$a_{t}\in\mathcal{L}$.

  * •

Case (i). Similar to Case 2, we continue to consider two cases:

    * –

if $\pi^{*}(x_{t})=\pi^{*}_{\mu}(x_{t})$ then

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{*}_{\mu}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\langle
x_{t},\hat{\theta}_{a_{t}}\rangle-\langle x_{t},\theta^{*}_{a_{t}}\rangle$
$\displaystyle\leq$ $\displaystyle\langle
x_{t},\hat{\theta}_{a_{t}}-\theta^{*}_{a_{t}}\rangle$ $\displaystyle\leq$
$\displaystyle||x_{t}||||\hat{\theta}_{a_{t}}-\theta^{\epsilon}_{a_{t}}||$
$\displaystyle\leq$ $\displaystyle\epsilon S_{x}$

    * –

if $\pi^{*}(x_{t})\not=\pi^{*}_{\mu}(x_{t})$ then $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle>\langle
x,\theta^{*}_{\pi^{*}_{\mu}(x)}\rangle$. Therefore, $\langle
x,\theta^{*}_{\pi^{*}(x)}\rangle=\langle x,\theta^{*}_{\pi^{+}(x)}\rangle$.

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-\langle
x_{t},\hat{\theta}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle+\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle
x_{t},\hat{\theta}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}+\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle-\langle
x_{t},\hat{\theta}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}+\epsilon
S_{x},$

where the first inequality, we use the assumption of Case 3 that $\langle
x_{t},\tilde{\theta}_{t,a_{t}}\rangle>r_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$.
In the last inequality, we use the proof similar as above (when
$\pi^{*}(x_{t})=\pi^{*}_{\mu}(x_{t})$ in Case 3).

  * •

Case (ii). We have

$\displaystyle\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle$ $\displaystyle=$ $\displaystyle\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\hat{\theta}_{a_{t}}\rangle$ $\displaystyle\leq$ $\displaystyle\epsilon
S_{x},$

where in the last inequality, we use the proof similar as above.

For all cases, we can summarize as follows:

$\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle=\begin{cases}r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle,&\text{or},\\\ 0,&\text{or},\\\
2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}},&\text{or},\\\
\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}+2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}},&\text{or},\\\
\epsilon S_{x},&\text{or},\\\ \langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-
r_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}+\epsilon
S_{x},&\text{or}.\end{cases}$ (4)

Thus, the regret of the $\epsilon$-mOFUL-IPS is bounded as

$\displaystyle\sum_{t=1}^{T}(\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{a_{t}}\rangle)\leq\underbrace{\sum_{t\in
B_{1}}(r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle)}_{\text{Term
1}}+\underbrace{\sum_{t\in B_{2}}\epsilon S_{x}}_{\text{Term 2}}+$
$\displaystyle+\underbrace{\sum_{t\in
B_{3}}2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}}}_{\text{Term
3}}+\underbrace{\sum_{t\in B_{4}}(\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\})}_{\text{Term
4}},$

where the index sets $B_{1}$, $B_{2}$, $B_{3}$ and $B_{4}$ are defined as

$B_{1}=\\{1\leq t\leq T|\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle\leq
r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle\\},$

$B_{2}=\\{1\leq t\leq T|\epsilon S_{x}\text{ exists in the upper bound of
}\langle x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle\text{ in Eq (3)}\\},$

$B_{3}=\\{1\leq t\leq
T|2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}}\text{
exists in the upper bound of }\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle\text{ in Eq (3)}\\},$

$B_{4}=\\{1\leq t\leq T|\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\langle
x_{t},\theta^{*}_{a_{t}}\rangle\leq\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}\\}.$

A constraint is $|B_{1}|+|B_{2}|+|B_{3}|+|B_{4}|=T$.

Bounding Term 1: if $B_{1}=\emptyset$ then Term 1 is zero. Assume that
$B_{1}\not\emptyset$. We apply Hoeffding’s bound to the random variable
$X_{t}=r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$
for every $t\in B_{1}$. We note that $(x^{\mu}_{i},a^{\mu}_{i},r^{\mu}_{i})\in
S$ and $x_{t}=x^{\mu}_{i}$. Set $\hat{V}_{T}=\frac{1}{|B_{1}|}\sum_{t\in
B_{1}}r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}$.
We have $|\hat{V}_{T}-\mathbb{E}[\hat{V}_{T}]|\leq
M\sqrt{\frac{ln(2/\delta)}{2|B_{1}|}}$. Therefore, $\hat{V}_{T}\leq
M\sqrt{\frac{ln(2/\delta)}{2|B_{1}|}}+\mathbb{E}[\hat{V}_{T}]$. Similar to the
proof of Lemma 3.1 of Strehl et al. [2010], we have
$\mathbb{E}[\hat{V}_{T}]\leq R^{+}(\pi^{+})$. Thus, we have

$\sum_{t\in
B_{1}}(r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle)\leq
M\sqrt{\frac{ln(2/\delta)}{2|B_{1}|}}+R^{+}(\pi^{+})-\sum_{t\in B_{1}}\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle.$

Further, we have $\mathbb{E}[\frac{1}{|B_{1}|}\sum_{i=1}^{|B_{1}|}\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle]=R^{+}(\pi^{+})$. Again, we apply
Hoeffding’s bound to $|B_{1}|$ random variables $\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle$. We have
$|\frac{1}{|B_{1}|}\sum_{i=1}^{|B_{1}|}\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-R^{+}(\pi^{+})|\leq\sqrt{\frac{ln(2/\delta)}{|B_{1}|}}$
with probability at least $1-\delta$.

Thus, $\sum_{t\in
B_{1}}(r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\}-\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle)\leq\mathcal{O}(\sqrt{\frac{ln(2/\delta)}{|B_{1}|}})$
with probability at least $1-\delta$.

Bounding Term 2: $\sum_{t\in B_{2}}\epsilon S_{x}=\epsilon S_{x}|B_{2}|$.

Bounding Term 3: By the proof similar as the one of Term 2 of Theorem 2,
$\sum_{t\in
B_{3}}2\sqrt{\beta_{t-1}(\delta)}||x_{t}||_{\overline{V}^{-1}_{t-1,a}}\leq\mathcal{O}(\sqrt{(K-L)|B_{3}|})$
with probability $1-\delta$.

Bounding Term 4: if $B_{4}=\emptyset$ then Term 4 is zero. Assume that
$B_{4}\not=\emptyset$. We apply Lemma 1 for a set of $|B_{4}|$ samples
$\\{(x_{t_{1}},a_{t_{1}}),...,\\}$, we achieve

$\sum_{t\in B_{4}}(\langle
x_{t},\theta^{*}_{\pi^{+}(x_{t})}\rangle-r^{\mu}_{i}\text{min}\\{\frac{\pi^{+}(a^{\mu}_{i}|x^{\mu}_{i})}{\mu(a^{\mu}_{i}|x^{\mu}_{i})},M\\})\leq\mathcal{O}(\sqrt{Var_{\pi}log(N(1/|B_{4}|,\mathcal{F}_{\Pi},2|B_{4}|)/\delta)/|B_{4}|}),$

with probability $1-\delta$.

Finally, with probability at least $1-\delta$, we get that
$\sum_{t=1}^{T}(\langle
x_{t},\theta^{*}_{\pi^{*}(x_{t})}\rangle-\sum_{t=1}^{T}\langle
x_{t},\theta^{*}_{a_{t}}\rangle)\leq\mathcal{O}(\epsilon
S_{x}|B_{2}|+\sqrt{(K-L)|B_{3}|}+\sqrt{Var_{\pi}log(N(1/|B_{4}|,\mathcal{F}_{\Pi},2|B_{4}|)/\delta)|B_{4}|})$.


Comparison of vertical temperature profiles, produced by the model, with diffusivity profile EXP (dark blue) and STAB (orange). The top panel shows the vertical profile every two hours, shifted by 1K per hour along the horizontal axis. The bottom panels show the temperature difference $\Delta$T with respect to the foundation temperature as a function of depth and time for the EXP model (left) and STAB model (right).

§ BAYESIAN INFERENCE

Consider a model $\mathcal{M}(\Theta)$ controlled by the parameter set $\Theta$.
Given the data $\mathcal{D}$, the probability that a certain value of $\Theta$ represents the truth follows from Bayes' rule,

\begin{align}
P(\Theta | \mathcal D) = \frac{P(\mathcal D | \Theta) P(\Theta)}{P(\mathcal D)} \ .
\end{align}

Here $P(A|B)$ denotes the conditional probability of $A$ given $B$. On the right-hand side, $P(\mathcal D|\Theta)$ is the likelihood of observing the data under the assumption that $\Theta$ represents the true model. The prior probability $P(\Theta)$ quantifies our knowledge of the parameter set before observing the data. Lastly, the denominator states the probability of the data being true, which is independent of the choice of model and merely adds a normalization factor. Hence the posterior probability $P(\Theta | \mathcal{D})$ is proportional to the product of the likelihood times the prior probability.

In practice, inferring the posterior distribution $P(\Theta | \mathcal{D})$ of the parameters $\Theta$ from the data $\mathcal{D}$ involves three steps: 1) construct the prior distribution $P(\Theta)$ in parameter space based on previous knowledge or belief; 2) define a suitable likelihood function $\mathcal L(\Theta) \equiv P(\mathcal D |\Theta)$; and 3) compute the (un-normalized) posterior distribution by evaluating the product $\mathcal{L}(\Theta)P(\Theta)$.

§.§ Choice of prior

Our sensitivity study under idealized forcing (section <ref>) provides orientation on physical ranges of the parameters $\{\kappa_0 , \, \mu, \, \alpha \}$ of the DiuSST model. In the literature, common values of oceanic turbulent vertical diffusivity are on the order of $\kappa \sim \SI{e-4}{\square\meter\per\second}$, varying with location and depth <cit.>.
Stating a physical value for the attenuation coefficient $\alpha$ is difficult since, in reality, attenuation of shortwave radiation depends strongly on wavelength and the biochemical composition of the seawater.
Empirical values for the diffusive attenuation coefficient of photosynthetically active radiation range from $\sim \SI{e-2}{\per\meter}$ to 10 <cit.>.
However, we note that the model parameters are conceptual, particularly the mixing coefficient $\mu$, such that they do not necessarily represent directly observable physical quantities.

Reflecting our limited knowledge, we impose uniform prior distributions for the parameters $\kappa_0$ and $\alpha$ but constrain their range to $\kappa \in [0,\, \SI{5e-4}]$ □ and $\alpha \in [0.05,\, 10]$ .
The parameter $\mu$ requires more subtle treatment because it acts mainly near the foundation depth, whereas the likelihood function evaluates temperature differences near the surface (see below).
Fig. <ref> indicates that excess heat remains in the interior of the diurnal layer if $\mu$ falls below $\sim \SI{1e-4}{\meter\per\second}$.
Based on this insight, we define a normally distributed prior for $\mu$ with mean $\SI{6e-3}{\meter\per\second}$ and standard deviation 1.5e-3.
Thus the three-dimensional prior distribution $P(\Theta)$ is uniform and bounded along the $\kappa_0$ and $\alpha$ directions but Gaussian with respect to $\mu$.

Note that the posterior distribution with respect to $\mu$ differs clearly from the prior distribution, confirming that the data added information on the parameter $\mu$ (Fig. <ref>).

§.§ Defining the likelihood function

Our training data $\mathcal{D}$ consists of a six-day subset of the diurnal warming time series from the MOCE-5 cruise, as indicated by the gray shading in Fig. <ref>.
Specifically, we select days 2-4 and 13-15 of October 1999 as training data, while all other days from 1 to 16 October make up the validation data.
By this choice, the training data contains warming events of different amplitudes, covering the observed range from a few tenths of a Kelvin up to 5K.
Moreover, the two sub-intervals composing $\mathcal{D}$ correspond to different geographical regions (open Pacific vs. Gulf of California), presumably featuring differing environmental conditions.
This ensures that the resulting parameter estimates will be valid for a broader range of conditions.

We choose a likelihood function that decays exponentially with the weighted square error between model and data,

\begin{align} \label{eq:likelihood}
\mathcal{L} \propto \exp \left( - \sum_{j} \frac{\big( \Delta \text{SST}_\mathcal{M}(t_j) - \Delta\text{SST}_\mathcal{D}(t_j) \big)^2}{\Sigma_j^2} \right) \ ,
\end{align}

where the index $j$ runs through all data points in $\mathcal{D}$ and $\Delta\text{SST}_\mathcal{M}$ ($\Delta\text{SST}_\mathcal{D}$) denotes the modeled (observed) diurnal warming at the corresponding time of observation. Specifically, $\Delta\text{SST}_\mathcal{M}(t_j) = T(0,t_j)-T(z_d,t_j)$, with $z_d$ being the depth of the vertical grid point closest to the observational reference depth $d = \SI{-3}{m}$.
Furthermore, the standard error $\Sigma_j$ determining the relative weight of the $j$-th data point is defined as

\begin{align}
\Sigma_j = 2\epsilon_j (1+v_j/v_\text{max}) \ ,
\end{align}

where $\epsilon_j$ denotes the uncertainty of the 3m temperature measurement, as stated in the data set; $v_j$ is the current boat speed and $v_\text{max}$ is the maximum boat speed throughout the data set. This choice reflects a reduced confidence in measurements taken while the ship was moving rapidly. Indeed, the MOCE-5 time series features several short, isolated warming spikes of around 1-2°C during nighttime hours, which cannot be explained by atmospheric forcing but could have been caused by the boat's movement. Since the ship mainly moved at night while often remaining at fixed locations during the day, $\Sigma_j$ emphasizes daylight data.

§.§ Computing the posterior distribution

To approximate the posterior distribution, we perform Markov chain Monte Carlo (MCMC) sampling using the  package in Python <cit.>. It is based on the affine-invariant GW10 algorithm proposed by Goodman and Weare . The algorithm explores the parameter space with multiple interdependent walkers whose moves efficiently deal with correlations, yielding fast convergence.

At each step of the Markov chain, the likelihood function, Eq. (<ref>), is evaluated for each walker at its respective position $\Theta$ in parameter space.
Each evaluation requires simulating the model for the duration of the training data, which makes the sampling computationally expensive.
For each of 24 walkers we generate $4000$ steps, initialized at the value $\{ \kappa_0, \mu, \alpha \} = \{ \SI{e-4}{\square\meter\per\second}, \, \SI{6e-3}{\meter\per\second}, \, \SI{4}{\per\meter}\}$. Finding an auto-correlation length of around 50 steps, this gives around 80 independent samples.

We summarize the resulting parameter estimates in Tab. <ref>, listing common statistical estimators as obtained from the posterior distribution of the DiuSST (Fig. <ref>) and Slab (Fig. <ref>) models, respectively. Bayesian inference for the Slab model was performed in analogy to the DiuSST model but in a four-dimensional parameter space $\{h, S, \xi_1, \xi_2 \}$
and with the slab temperature anomaly representing $\Delta\text{SST}_\mathcal{M}$ in the likelihood function. The run was initialized at values $\{h, S, \xi_1, \xi_2 \} = \{1, 100, 10^{-4}, 10^{-9} \}$ with uniform priors for $h$, $\xi_1$, $\xi_2$ and a Gaussian prior for $S$ with mean 100□ and standard deviation 10□.

Model     Parameter     MAP     Mean     Median

DiuSST     $\kappa_0$ (□)     1.34e-4     1.41e-4     1.40e-4

$\mu$ ()     2.85e-3     3.00e-3     2.96e-3

$\alpha$ ()     3.52     3.83     3.70

Slab     $h$ (m)     1.20     1.20     1.20

$S$ (□)     92.67     93.86     93.94

$\xi_1$     1.19e-4     1.20e-4     1.18e-4

$\xi_2$     3.1e-11     5.3e-11     3.7e-11

Parameter estimates obtained from the sampled posterior distribution.

Posterior distribution for the parameters of the slab model, obtained from Bayesian MCMC sampling. Compare with Fig. <ref>, which shows the results for the DiuSST model.

§ SLAB MODEL: PARAMETER SENSITIVITY

As mentioned in the main text, the Bayesian optimization procedure applied to the Slab model acts mainly by ramping up the relaxation parameter $\xi_1$, which constrains diurnal warming to 1K. Larger diurnal amplitudes are achieved by reducing $\xi_1$ (see Fig. <ref>). However, in that case the slab also cools excessively at night, and the diurnal warming peak shifts into the late afternoon, with a slow temperature decrease after peak warming.

Performance of the slab model as a function of its control parameter $\xi_1$. The solid red (Model) and blue (Slab A) lines show simulations of our calibrated model and the slab model, respectively, with parameter values given in table <ref>. The orange curve (Slab B) shows a slab simulation with $h=\SI{1.1}{m}$, $S=\SI{70}{\watt\per\square\meter}$, $\xi_1=\SI{1e-7}{}$ and $\xi_2=0$. Note that for Slab B, $\xi_1$ is three orders of magnitude smaller compared to Slab A.

§ MODEL COMPARISON OVER FULL MOCE5 TIME SERIES

Comparison of observed diurnal warming $\Delta$SST (light blue) against the predictions of the calibrated DiuSST (red dashed), ZB05 (dark blue), and calibrated Slab (orange dash-dotted) models, showing the full 16-day time series recorded on the MOCE-5 cruise.