# A Correction of Pseudo Log-Likelihood Method

Shi Feng  Harvard University, MA, USA  Nuoya Xiong  Institute for
Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Zhijie Zhang  School of Mathematics and Statistics, Fuzhou University, Fuzhou,
China  Wei Chen Corresponding author<EMAIL_ADDRESS>Microsoft Research,
Beijing, China

###### Abstract

Pseudo log-likelihood is a type of maximum likelihood estimation (MLE) method
used in various fields including contextual bandits, influence maximization of
social networks, and causal bandits. However, in previous literature (Li et
al., 2017; Zhang et al., 2022a; Xiong and Chen, 2022; Feng and Chen, 2023;
Feng et al., 2023), the log-likelihood function may not be bounded, which may
result in the algorithm they proposed not well-defined. In this paper, we give
a counterexample that the maximum pseudo log-likelihood estimation fails and
then provide a solution to correct the algorithms in (Li et al., 2017; Zhang
et al., 2022a; Xiong and Chen, 2022; Feng and Chen, 2023; Feng et al., 2023).

##  1 Problem Description

In (Li et al., 2017; Zhang et al., 2022a; Xiong and Chen, 2022; Feng and Chen,
2023; Feng et al., 2023), the authors use the same maximum likelihood
estimation (MLE) method. Suppose $X_{1},X_{2},\ldots,X_{d}$ are random
variables such that $X_{i}\in[0,1]$. For convenience, we use $\boldsymbol{X}$
to denote the vector $(X_{1},X_{2},\cdots,X_{d})$. The function $\mu$ is a
monotone increasing and second-order differentiable function from $\mathbb{R}$
to $\mathbb{R}$, and $m(x)$ is defined as:

$m(x)=\begin{cases}\int_{0}^{x}\mu(x^{\prime})\mathsf{d}x^{\prime}&x\geq 0\\\
-\int_{-x}^{0}\mu(x^{\prime})\mathsf{d}x^{\prime}&x<0\end{cases}.$

There is a set of parameters
$\theta^{*}_{1},\theta^{*}_{2},\ldots,\theta^{*}_{d}$, which we also denote by
vector $\boldsymbol{\theta}^{*}$. Moreover, $Y\in[0,1]$ is the outcome of
$X_{1},X_{2},\ldots,X_{d}$ such that
$\mathbb{E}[Y|\boldsymbol{X}]=\mu(\boldsymbol{X}^{\intercal}\boldsymbol{\theta}^{*})$.
$Y$ depends on $\boldsymbol{X}^{\intercal}\boldsymbol{\theta}^{*}$ and its
noise term is independent of $\boldsymbol{X}$ and $\boldsymbol{\theta}^{*}$.

There are in total $t$ rounds and in the $i^{th}$ round, the values of
$X_{1},X_{2},\ldots,X_{d}$ are $x_{1,i},x_{2,i},\ldots,x_{d,i}$, and the value
of $Y$ is $y_{i}$. For convenience, we denote the vector
$(x_{1,i},x_{2,i},\ldots,x_{d,i})$ by $\boldsymbol{x}_{i}$. To estimate
$\boldsymbol{\theta}^{*}$, the MLE method (Li et al., 2017; Zhang et al.,
2022a) takes

$\displaystyle\hat{\boldsymbol{\theta}}_{t}=\operatorname*{argmax}_{\boldsymbol{\theta}\in\mathbb{R}^{d}}\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
(1)

as the estimation of $\boldsymbol{\theta}^{*}$. Since $m$ is a second-order
differentiable function, when $\hat{\boldsymbol{\theta}}_{t}$ is a maximum of

$\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right),$

the gradient
$\sum_{i=1}^{t}(y_{i}-\mu(\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}))\boldsymbol{x}_{i}$
should be $\mathbf{0}$. In (Xiong and Chen, 2022; Feng and Chen, 2023; Feng et
al., 2023), they solve $\hat{\boldsymbol{\theta}}_{t}$ by the equation
$\sum_{i=1}^{t}(y_{i}-\mu(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}))\boldsymbol{x}_{i}=\mathbf{0}$.

Theorem 1 in (Li et al., 2017), Theorem 3 in (Zhang et al., 2022b), and Lemma
1 in (Feng and Chen, 2023) provide a guarantee for the distance from
$\hat{\boldsymbol{\theta}}_{t}$ to $\boldsymbol{\theta}^{*}$ when
$\hat{\boldsymbol{\theta}}_{t}$ exists. However, none of these previous
literature (Li et al., 2017; Zhang et al., 2022a; Xiong and Chen, 2022; Feng
and Chen, 2023; Feng et al., 2023) discusses the existence of
$\hat{\boldsymbol{\theta}}_{t}$, i.e., whether
$\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
could tend to positive infinity when some elements of $\boldsymbol{\theta}$
tend to infinity. If $\hat{\boldsymbol{\theta}}_{t}$ does not exist, the
deductions in all the previous literature collapse. In this short paper, we
present a counterexample to show that $\hat{\boldsymbol{\theta}}_{t}$ may not
exist under the conditions of the previous papers (Li et al., 2017; Zhang et
al., 2022a; Xiong and Chen, 2022; Feng and Chen, 2023; Feng et al., 2023) and
provide a solution to address this issue. For consistency, we will use the
notations in this section throughout this paper. Readers can correlate the
notations with those of previous papers.

##  2 Counter-Examples

In this section, we present a counterexample to demonstrate the incorrectness
of the default assumption that $\hat{\boldsymbol{\theta}}_{t}$ exists. In (Li
et al., 2017), $X_{1},\ldots,X_{d},Y$ are continuous variables in $[0,1]$. In
our counterexample, we let the link function be $\mu(x)=\frac{1}{2+2e^{-x}}$,
which satisfies Assumptions 1 and 2 in (Li et al., 2017). For convenience, we
denote
$\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
by $H(\boldsymbol{\theta})$.

When $x_{1,i}=x_{2,i}=\cdots=x_{d,i}>0$ and $y_{i}>\frac{1}{2}$ for
$i=1,2,\ldots,t$, the $j^{th}$ element of the gradient of
$H(\boldsymbol{\theta})$ satisfies:

$\displaystyle\frac{\partial
H(\boldsymbol{\theta})}{\partial\theta_{j}}=\left(\sum_{i=1}^{t}(y_{i}-\mu(\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}))\boldsymbol{x}_{i}\right)_{j}$
$\displaystyle=\sum_{i=1}^{t}(y_{i}-\mu(\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}))x_{j,i}$
$\displaystyle>\sum_{i=1}^{t}\left(\frac{1}{2}-\frac{1}{2+2e^{-\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}}}\right)x_{j,i}$
$\displaystyle>0.$

This occurs with a nonzero probability111In (Li et al., 2017), the first
$\tau$ rounds of Algorithm 1 are random., and it indicates that
$\lim_{\theta_{1}\rightarrow+\infty,\ldots,\theta_{d}\rightarrow+\infty}H(\boldsymbol{\theta})=+\infty$
and thus Eq.(1) does not have a solution. This is a contradiction, and
therefore, the proof of Theorem 1 in (Li et al., 2017) collapses.222Even when
$\boldsymbol{\theta}$ is bounded, this is still a contradiction because the
proof of Theorem 1 in (Li et al., 2017) uses
$\nabla_{\boldsymbol{\theta}}H(\boldsymbol{\theta})={\bf 0}$.

In (Zhang et al., 2022a; Xiong and Chen, 2022; Feng and Chen, 2023; Feng et
al., 2023), $X_{1},\ldots,X_{d},Y$ are binary variables. In our
counterexample, we let $\mu(x)=1-e^{-x}$, satisfying all assumptions in these
papers. When $x_{1,i}=x_{2,i}=\cdots=x_{d,i}=1$ and $y_{i}=1$ for
$i=1,2,\ldots,t$, the $j^{th}$ element of the gradient of
$H(\boldsymbol{\theta})$ satisfies:

$\displaystyle\frac{\partial
H(\boldsymbol{\theta})}{\partial\theta_{j}}=\left(\sum_{i=1}^{t}(y_{i}-\mu(\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}))\boldsymbol{x}_{i}\right)_{j}$
$\displaystyle=\sum_{i=1}^{t}(y_{i}-\mu(\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}))x_{j,i}$
$\displaystyle>\sum_{i=1}^{t}e^{-\boldsymbol{x}_{i}^{\intercal}\hat{\boldsymbol{\theta}}_{t}}>0.$

This also occurs with a nonzero probability and it indicates that
$\lim_{\theta_{1}\rightarrow+\infty,\ldots,\theta_{d}\rightarrow+\infty}H(\boldsymbol{\theta})=+\infty$
and thus Eq.(1) does not have a solution. This is a contradiction, and
therefore, the proofs of Theorem 3 in (Zhang et al., 2022a) and Lemma 1 in
(Feng and Chen, 2023) collapses. Furthermore, the regret analysis in (Zhang et
al., 2022a; Xiong and Chen, 2022; Feng and Chen, 2023; Feng et al., 2023)
collapse.333In (Xiong and Chen, 2022), only the regret analysis of Algorithm 1
uses the MLE method in Eq.(1) and collapses due to this counterexample.

##  3 The Solution

In this section, we provide a feasible solution to promise the existence of
$\hat{\boldsymbol{\theta}}_{t}$, which fixes the issues in the analysis of the
five previous papers we mentioned in Section 1. Before our solution, one
should notice that the constraint on $\mu$ in all five previous papers is
Assumptions $1$ and $2$ in (Li et al., 2017).

######  Assumption 1 (Assumption 1 in (Li et al., 2017)).

$\kappa:=\mathsf{inf}_{\boldsymbol{x}\in[0,1]^{d},\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|\leq
1}\mu^{\prime}(\boldsymbol{x}^{\intercal}\boldsymbol{\theta})>0$.444Li et al.
(2017) use a weaker version with $\left\|\boldsymbol{x}\right\|\leq 1$. The
other four papers use the current stronger version.

######  Assumption 2 (Assumption 2 in (Li et al., 2017)).

Function $\mu$ is twice differentiable. Its first and second-order derivatives
are upper-bounded by $L_{\mu}$ and $M_{\mu}$, respectively.

In summary, our solution is replacing function $\mu$ by another function $h$
in the algorithm such that the following conditions hold:
$\lim_{x\rightarrow+\infty}h(x)=+\infty$,
$\lim_{x\rightarrow-\infty}h(x)=-\infty$, $h$ is monotone increasing and twice
differentiable, $h$ satisfies Assumptions 1 and 2, and when $x$ is in the
range
$\left[-\sum_{i=1}^{d}\mathsf{ReLU}(-\theta^{*}_{i}),\sum_{i=1}^{d}\mathsf{ReLU}(\theta^{*}_{i})\right]$555$\mathsf{ReLU}(x)=\max\\{0,x\\}$
and $\boldsymbol{X}^{\intercal}\boldsymbol{\theta}^{*}$ has to be in this
interval., $h(x)=\mu(x)$.

We firstly prove that $\mu$ can be converted to a monotone increasing function
$g$ satisfying $\lim_{x\rightarrow+\infty}g(x)=+\infty$. If we already have
$\lim_{x\rightarrow+\infty}\mu(x)=+\infty$, we can directly let $g\equiv\mu$.
Otherwise, $\mu$ has an upper bound. In (Zhang et al., 2022a; Xiong and Chen,
2022; Feng and Chen, 2023; Feng et al., 2023), $\theta^{*}_{i}\in[0,1]$ so
each $\theta^{*}_{i}$ is bounded. In (Li et al., 2017), since $\mu$ is upper-
bounded, we know that $\lim_{x\rightarrow+\infty}\mu^{\prime}(x)=0$. According
to Assumption 1,
$\theta^{*}_{i}\leq\max\\{x:\mu^{\prime}(x)=\kappa\\}-1$.666Otherwise, when
$x_{j}=0$ if $j\neq i$, $x_{i}=1$ and
$\theta_{i}^{*}>\max\\{x:\mu^{\prime}(x)=\kappa\\}-1,\theta_{i}=\theta_{i}^{*}+1>\max\\{x:\mu^{\prime}(x)=\kappa\\}$,
we have
$\boldsymbol{x}^{\intercal}\boldsymbol{\theta}>\max\\{x:\mu^{\prime}(x)=\kappa\\}$
and thus $\mu^{\prime}(\boldsymbol{x}^{\intercal}\boldsymbol{\theta})<\kappa$,
which is a contradiction to Assumption 1. Therefore,
$\sum_{i=1}^{d}\mathsf{ReLU}(\theta^{*}_{i})$ is also upper-bounded in this
case, we denote the upper bound by $U$. We find a $x^{*}\geq U+d$ such that
$\mu^{\prime\prime}(x^{*})<0$. If $x^{*}$ does not exist, we know that
$\mu(x)\geq\mu(U+d)+\mu^{\prime}(U+d)(x-(U+d))$ when $x\geq U+d$, which is
contradictory to $\mu$ is upper-bounded. Hence, when $\mu$ is upper-bounded,
we define the conversion as

$\displaystyle g(x)=\begin{cases}\mu(x)&x\leq x^{*}\\\
\mu(x^{*})+\frac{\mu^{\prime}(x^{*})^{2}}{\mu^{\prime\prime}(x^{*})}\ln\left(-\frac{\mu^{\prime}(x^{*})}{\mu^{\prime\prime}(x^{*})}\right)-\frac{\mu^{\prime}(x^{*})^{2}}{\mu^{\prime\prime}(x^{*})}\ln\left(x-x^{*}-\frac{\mu^{\prime}(x^{*})}{\mu^{\prime\prime}(x^{*})}\right)&x>x^{*}\end{cases}.$

######  Lemma 1.

By doing the conversion above, we can replace function $\mu$ by $g$ such that
$\lim_{x\rightarrow+\infty}g(x)=+\infty$, $g$ is monotone increasing and twice
differentiable, $g$ satisfies Assumptions 1 and 2, and when $x$ is in the
range
$\left[-\sum_{i=1}^{d}\mathsf{ReLU}(-\theta^{*}_{i}),\sum_{i=1}^{d}\mathsf{ReLU}(\theta^{*}_{i})\right]$,
$g(x)=\mu(x)$.

###### Proof.

When $\mu$ is not upper-bounded, we let $g\equiv\mu$ so the claim is proved.
When $\mu$ is upper-bounded, during the producing process of $Y$, the input of
$\mu$ is $\boldsymbol{X}\cdot\boldsymbol{\theta}^{*}$, which is in the range
$\left[-\sum_{i=1}^{d}\mathsf{ReLU}(-\theta^{*}_{i}),\sum_{i=1}^{d}\mathsf{ReLU}(\theta^{*}_{i})\right]\subseteq(-\infty,U]$.
Hence, when we replace $\mu$ with $g$, the joint conditional distribution of
$Y$ on $\boldsymbol{X}$ is not impacted.

Moreover, we can compute that

$\displaystyle g^{\prime}(x)=\begin{cases}\mu^{\prime}(x)&x\leq x^{*}\\\
-\frac{\mu^{\prime}(x^{*})^{2}}{\mu^{\prime\prime}(x^{*})\left(x-x^{*}-\frac{\mu^{\prime}(x^{*})}{\mu^{\prime\prime}(x^{*})}\right)}&x>x^{*}\end{cases},$

and

$\displaystyle g^{\prime\prime}(x)=\begin{cases}\mu^{\prime\prime}(x)&x\leq
x^{*}\\\
\frac{\mu^{\prime}(x^{*})^{2}}{\mu^{\prime\prime}(x^{*})\left(x-x^{*}-\frac{\mu^{\prime}(x^{*})}{\mu^{\prime\prime}(x^{*})}\right)^{2}}&x>x^{*}\end{cases}.$

Therefore, we have $\lim_{x\rightarrow{x^{*}}^{+}}g(x)=\mu(x^{*})$ and
$\lim_{x\rightarrow{x^{*}}^{-}}g(x)=\mu(x^{*})$. Hence, $g$ is continuous.
Moreover,
$\lim_{x\rightarrow{x^{*}}^{+}}g^{\prime}(x)=\mu^{\prime}(x^{*})=\lim_{x\rightarrow{x^{*}}^{-}}g^{\prime}(x)$
and
$\lim_{x\rightarrow{x^{*}}^{+}}g^{\prime\prime}(x)=\mu^{\prime\prime}(x^{*})=\lim_{x\rightarrow{x^{*}}^{-}}g^{\prime\prime}(x)$,
so $g(x)$ is twice differentiable and $g^{\prime\prime}$ is continuous.

Now we only need to verify Assumptions 1 and 2. Firstly, when $x>x^{*}$, we
have $g^{\prime}(x)<g^{\prime}(x^{*})=\mu^{\prime}(x^{*})\leq L\mu$ and
$g^{\prime\prime}(x)<g^{\prime\prime}(x^{*})=\mu^{\prime\prime}(x^{*})\leq
M_{\mu}$, so Assumption 2 holds. Secondly,
$\max_{\boldsymbol{x}\in[0,1]^{d},\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|\leq
1}\boldsymbol{x}\cdot\boldsymbol{\theta}\leq U+d\leq x^{*}$, so the conversion
does not impact the value of $\kappa$. The claim then follows. ∎

We secondly prove that $g$ can be converted to a monotone increasing function
$h$ satisfying $\lim_{x\rightarrow+\infty}h(x)=+\infty$ and simultaneously,
$\lim_{x\rightarrow-\infty}h(x)=-\infty$. If we already have
$\lim_{x\rightarrow-\infty}\mu(x)=-\infty$, we can directly let $h\equiv g$.
Otherwise, $\mu$ has a lower bound. In (Zhang et al., 2022a; Xiong and Chen,
2022; Feng and Chen, 2023; Feng et al., 2023), $\theta^{*}_{i}\in[0,1]$ so
each $\theta^{*}_{i}$ is bounded. In (Li et al., 2017), since $\mu$ is lower-
bounded, we know that $\lim_{x\rightarrow-\infty}\mu^{\prime}(x)=0$. According
to Assumption 1, $\theta^{*}_{i}\geq\min\\{x:\mu^{\prime}(x)=\kappa\\}+1$.
777Otherwise, when $x_{j}=0$ if $j\neq i$, $x_{i}=1$ and
$\theta_{i}^{*}<\min\\{x:\mu^{\prime}(x)=\kappa\\}+1,\theta_{i}=\theta_{i}^{*}-1<\min\\{x:\mu^{\prime}(x)=\kappa\\}$,
we have
$\boldsymbol{x}^{\intercal}\boldsymbol{\theta}<\min\\{x:\mu^{\prime}(x)=\kappa\\}$
and thus $\mu^{\prime}(\boldsymbol{x}^{\intercal}\boldsymbol{\theta})<\kappa$,
which is a contradiction to Assumption 1. Therefore,
$-\sum_{i=1}^{d}\mathsf{ReLU}(-\theta^{*}_{i})$ is also lower-bounded in this
case, we denote the lower bound by $L$. We find a $x^{**}\leq L-d$ such that
$\mu^{\prime\prime}(x^{**})>0$. If $x^{**}$ does not exist, we know that
$\mu(x)\leq\mu(L-d)+\mu^{\prime}(L-d)(x-(L-d))$ when $x\leq L-d$, which is
contradictory to $\mu$ is lower-bounded. Hence, when $\mu$ is lower-bounded,
We define the conversion as

$\displaystyle h(x)=\begin{cases}g(x)&x\geq x^{**}\\\
g(x^{**})-\frac{g^{\prime}(x^{**})^{2}}{g^{\prime\prime}(x^{**})}\ln\left(-\frac{g^{\prime}(x^{**})}{g^{\prime\prime}(x^{**})}\right)+\frac{g^{\prime}(x^{**})^{2}}{g^{\prime\prime}(x^{**})}\ln\left(-x+x^{**}+\frac{g^{\prime}(x^{**})}{g^{\prime\prime}(x^{**})}\right)&x<x^{**}\end{cases}.$

######  Lemma 2.

By doing the conversion above, we can replace function $\mu$ by $h$ such that
$\lim_{x\rightarrow+\infty}h(x)=+\infty$,
$\lim_{x\rightarrow-\infty}h(x)=-\infty$, $h$ is monotone increasing and twice
differentiable, $h$ satisfies Assumptions 1 and 2, and when $x$ is in the
range
$\left[-\sum_{i=1}^{d}\mathsf{ReLU}(-\theta^{*}_{i}),\sum_{i=1}^{d}\mathsf{ReLU}(\theta^{*}_{i})\right]$,
$h(x)=\mu(x)$.

###### Proof.

When $\mu$ is not lower-bounded, we let $h\equiv g$ so the claim is proved by
Lemma 1. When $\mu$ is lower-bounded, during the producing process of $Y$, the
input of $\mu$ is $\boldsymbol{X}\cdot\boldsymbol{\theta}^{*}$, which is in
the range
$\left[-\sum_{i=1}^{d}\mathsf{ReLU}(-\theta^{*}_{i}),\sum_{i=1}^{d}\mathsf{ReLU}(\theta^{*}_{i})\right]\subseteq[-L,+\infty)$.
Hence, combining Lemma 1, when we replace $\mu$ with $h$, the joint
conditional distribution of $Y$ on $\boldsymbol{X}$ is not impacted.

Moreover, we can compute that

$\displaystyle h^{\prime}(x)=\begin{cases}g^{\prime}(x)&x\geq x^{**}\\\
\frac{g^{\prime}(x^{**})^{2}}{g^{\prime\prime}(x^{**})\left(-x+x^{**}+\frac{g^{\prime}(x^{**})}{g^{\prime\prime}(x^{**})}\right)}&x<x^{**}\end{cases},$

and

$\displaystyle h^{\prime\prime}(x)=\begin{cases}g^{\prime\prime}(x)&x\geq
x^{**}\\\
\frac{g^{\prime}(x^{**})^{2}}{g^{\prime\prime}(x^{**})\left(x-x^{**}-\frac{g^{\prime}(x^{**})}{g^{\prime\prime}(x^{**})}\right)^{2}}&x<x^{**}\end{cases}.$

Therefore, we have $\lim_{x\rightarrow{x^{**}}^{+}}h(x)=g(x^{**})$ and
$\lim_{x\rightarrow{x^{**}}^{-}}h(x)=g(x^{**})$. Hence, $h$ is continuous.
Moreover,
$\lim_{x\rightarrow{x^{**}}^{+}}h^{\prime}(x)=g^{\prime}(x^{**})=\lim_{x\rightarrow{x^{**}}^{-}}h^{\prime}(x)$
and
$\lim_{x\rightarrow{x^{**}}^{+}}h^{\prime\prime}(x)=g^{\prime\prime}(x^{**})=\lim_{x\rightarrow{x^{**}}^{-}}h^{\prime\prime}(x)$,
so $h(x)$ is twice differentiable and $h^{\prime\prime}$ is continuous.

Now we only need to verify Assumptions 1 and 2. Firstly, when $x<x^{**}$, we
have $h^{\prime}(x)<h^{\prime}(x^{**})=g^{\prime}(x^{**})\leq L_{\mu}$ and
$h^{\prime\prime}(x)<h^{\prime\prime}(x^{**})=g^{\prime\prime}(x^{**})\leq
M_{\mu}$, so Assumption 2 holds. Secondly,
$\min_{\boldsymbol{x}\in[0,1]^{d},\left\|\boldsymbol{\theta}-\boldsymbol{\theta}^{*}\right\|\leq
1}\boldsymbol{x}\cdot\boldsymbol{\theta}\geq L-d\geq x^{**}$, so the
conversion does not impact the value of $\kappa$. Until now, the claim has
been proven. ∎

Hence, we can replace $\mu$ by $h$ in the MLE method in (1) without impacting
the data distribution and our requirements on $\mu$. Finally, we prove that by
using $h$ in (1), the existence of $\hat{\boldsymbol{\theta}}_{t}$ is
promised. let

$m_{h}(x)=\begin{cases}\int_{0}^{x}h(x^{\prime})\mathsf{d}x^{\prime}&x\geq
0,\\\ -\int_{-x}^{0}h(x^{\prime})\mathsf{d}x^{\prime}&x<0.\end{cases}$

######  Lemma 3.

When $h$ is monotone increasing, $\lim_{x\rightarrow+\infty}h(x)=+\infty$, and
$\lim_{x\rightarrow-\infty}h(x)=-\infty$, the maximum of
$H_{h}(\boldsymbol{\theta})=\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
exists.

###### Proof.

We only need to prove that

$H_{h}(\boldsymbol{\theta})=\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$

is a concave function with respect to $\boldsymbol{\theta}$ and
$\lim_{(\boldsymbol{\theta})_{j}\rightarrow\infty}H_{h}(\boldsymbol{\theta})=-\infty$
or $\frac{\partial
H_{h}(\boldsymbol{\theta})}{\partial(\boldsymbol{\theta})_{j}}\equiv 0$ for
all $j\in[d]$, which implies that $H$ has a maximal point. Firstly, we know
that

$\displaystyle\frac{\partial^{2}m_{h}(x)}{\partial x^{2}}=h^{\prime}(x)>0,$

so $m_{h}$ is a convex function. Therefore, for any vectors
$\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}\in\mathbb{R}^{d}$ and
$\lambda\in[0,1]$, we have

$\displaystyle
m_{h}\left(\boldsymbol{x}_{i}^{\intercal}(\lambda\boldsymbol{\theta}_{1}+(1-\lambda)\boldsymbol{\theta}_{2})\right)$
$\displaystyle=m_{h}\left(\lambda\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}_{1}+(1-\lambda)\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}_{2})\right)$
$\displaystyle\leq\lambda
m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}_{1})+(1-\lambda)m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}_{2}),$

so $m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})$ is also a convex
function with respect to $\boldsymbol{\theta}$ and the Hessian matrix
$\mathbf{H}[m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})]$ of
$m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})$ with respect to
$\boldsymbol{\theta}$ should be positive semidefinite. Now we can compute the
Hessian matrix $\mathbf{H}[H_{h}(\boldsymbol{\theta})]$ as

$\displaystyle\mathbf{H}[H_{h}(\boldsymbol{\theta})]=\sum_{i=1}^{t}\left(-\boldsymbol{x}_{i}^{\intercal}\boldsymbol{x}_{i}\cdot\mathbf{H}[m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})]\right).$

Hence, $\mathbf{H}[H_{h}(\boldsymbol{\theta})]$ is negative semidefinite
because multiplying a positive semidefinite matrix by a negative scalar
preserves the semidefiniteness. Thus $H$ is a concave function with respect to
$\boldsymbol{\theta}$.

Now for any $j\in[d]$, we prove that
$\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow+\infty}H_{h}(\boldsymbol{\theta}_{X})=-\infty$
and
$\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow-\infty}H_{h}(\boldsymbol{\theta}_{X})=-\infty$
or $\frac{\partial
H_{h}(\boldsymbol{\theta})}{\partial(\boldsymbol{\theta})_{j}}\equiv 0$.
Firstly, we have

$\displaystyle\frac{\partial
H_{h}(\boldsymbol{\theta})}{\partial(\boldsymbol{\theta})_{j}}$
$\displaystyle=\sum_{i=1}^{t}\left(y_{i}(\boldsymbol{x}_{i})_{j}-(\boldsymbol{x}_{i})_{j}m_{h}^{\prime}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
$\displaystyle=\sum_{i=1}^{t}\left(y_{i}(\boldsymbol{x}_{i})_{j}-(\boldsymbol{x}_{i})_{j}h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right).$

If $(\boldsymbol{x}_{i})_{j}=0$ for all $i\in[t]$, we have $\frac{\partial
H_{h}(\boldsymbol{\theta})}{\partial(\boldsymbol{\theta})_{j}}\equiv 0$.
Otherwise, we have

$\displaystyle\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow+\infty}\frac{\partial
H_{h}(\boldsymbol{\theta})}{\partial(\boldsymbol{\theta})_{j}}$
$\displaystyle=\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow+\infty}\sum_{i=1}^{t}\left(y_{i}(\boldsymbol{x}_{i})_{j}-(\boldsymbol{x}_{i})_{j}h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
$\displaystyle=\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow+\infty}\sum_{i=1}^{t}(\boldsymbol{x}_{i})_{j}\left(y_{i}-h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
$\displaystyle=-\infty,$
($\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow+\infty}h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})=+\infty$)

which indicates that
$\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow+\infty}H_{h}(\boldsymbol{\theta}_{X})=-\infty$.
Also, we have

$\displaystyle\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow-\infty}\frac{\partial
H_{h}(\boldsymbol{\theta})}{\partial(\boldsymbol{\theta})_{j}}$
$\displaystyle=\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow-\infty}\sum_{i=1}^{t}\left(y_{i}(\boldsymbol{x}_{i})_{j}-(\boldsymbol{x}_{i})_{j}h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
$\displaystyle=\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow-\infty}\sum_{i=1}^{t}(\boldsymbol{x}_{i})_{j}\left(y_{i}-h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
$\displaystyle=+\infty,$
($\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow-\infty}h(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})=-\infty$)

which indicates that
$\lim_{(\boldsymbol{\theta}_{X})_{j}\rightarrow-\infty}H_{h}(\boldsymbol{\theta}_{X})=-\infty$.

Therefore, we have proved that $H_{h}(\boldsymbol{\theta})$ has at least one
global maximum, which indicates that the equation has at least one solution. ∎

In conclusion, by combining Lemmas 1, 2, and 3, we arrive at the following
main theorem:

######  Theorem 1 (Main Theorem).

Consider a monotone-increasing and twice differentiable function $\mu$ that
satisfies Assumptions 1 and 2. By transforming $\mu$ into the function $h$ as
described above, we ensure that $h$ remains monotone-increasing and twice
differentiable. Furthermore, $h$ preserves the same mapping in the range of
input $\boldsymbol{x}^{\intercal}\boldsymbol{\theta}^{*}$ and conforms to
Assumptions 1 and 2. Most importantly, the maximum of
$H_{h}(\boldsymbol{\theta})=\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
exists.

###### Proof.

According to Lemmas 1 and 2, it is established that $h$ remains monotone-
increasing and twice differentiable. Additionally, these lemmas confirm that
$h$ preserves the same mapping in the range of input
$\boldsymbol{x}^{\intercal}\boldsymbol{\theta}^{*}$ and conforms to
Assumptions 1 and 2. Furthermore, Lemmas 1 and 2 demonstrate that
$\lim_{x\rightarrow+\infty}h(x)=+\infty$ and
$\lim_{x\rightarrow-\infty}h(x)=-\infty$, satisfying the condition of Lemma 3.
Therefore, we can conclude that the maximum of
$H_{h}(\boldsymbol{\theta})=\sum_{i=1}^{t}\left(y_{i}\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta}-m_{h}(\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\theta})\right)$
indeed exists. ∎

##  4 Conclusion

In this paper, we identify and address an issue present in a type of Maximum
Likelihood Estimation (MLE) method commonly employed in previous studies.
Individuals intending to use similar methods in the future should be cautious
of the same or analogous issues. Furthermore, one might consider a more
intuitive and efficient solution to ensure the existence of
$\hat{\boldsymbol{\theta}}_{t}$, rather than artificially constructing a new
function.

## References

  * Feng and Chen (2023) S. Feng and W. Chen.  Combinatorial causal bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37(6), pages 7550–7558, 2023.
  * Feng et al. (2023) S. Feng, N. Xiong, and W. Chen.  Combinatorial causal bandits without graph skeleton.  _arXiv preprint arXiv:2301.13392v3_ , 2023.
  * Li et al. (2017) L. Li, Y. Lu, and D. Zhou.  Provably optimal algorithms for generalized linear contextual bandits.  In _International Conference on Machine Learning_ , pages 2071–2080. PMLR, 2017.
  * Xiong and Chen (2022) N. Xiong and W. Chen.  Combinatorial pure exploration of causal bandits.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Zhang et al. (2022a) Z. Zhang, W. Chen, X. Sun, and J. Zhang.  Online influence maximization with node-level feedback using standard offline oracles.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36(8), pages 9153–9161, 2022a.
  * Zhang et al. (2022b) Z. Zhang, W. Chen, X. Sun, and J. Zhang.  Online influence maximization under the independent cascade model with node-level feedback, 2022b.