# Directed Exploration in PAC Model-Free Reinforcement Learning

Min-hwan Oh  Garud Iyengar

###### Abstract

We study an exploration method for model-free RL that generalizes the counter-
based exploration bonus methods and takes into account long term exploratory
value of actions rather than a single step look-ahead. We propose a model-free
RL method that modifies Delayed Q-learning and utilizes the long-term
exploration bonus with provable efficiency. We show that our proposed method
finds a near-optimal policy in polynomial time (PAC-MDP), and also provide
experimental evidence that our proposed algorithm is an efficient exploration
method.

Machine Learning, ICML

##  1 Introduction

In reinforcement learning (RL), an agent, whose objective is to maximize the
expected sum of reward, initially starts to make decisions in an unknown
environment. It faces trials and errors while collecting reward and
information. However, it is not feasible for the agent to act near-optimally
until it has explored the environment sufficiently and identified all of the
opportunities for high reward. One of the fundamental challenges in RL is to
balance exploration and exploitation — whether to act not greedily action
according to current estimates in order to gain new information or to act
consistently with past experience to maximize reward.

Common dithering strategies, such as $\epsilon$-greedy, or sampling from a
Boltzmann distribution (Softmax) over the learned Q-values have been widely
applied to standard RL methods as exploration strategies. However these naive
approaches can lead to highly inefficient exploration, in the sense that they
waste exploration resources on actions and trajectories which are already well
known. In other words, they are not directed towards gaining more knowledge,
not biasing actions in the direction of unexplored trajectories (Thrun, 1992;
Little & Sommer, 2013; Osband et al., 2016).

In order to avoid wasteful exploration and guide toward more directed
exploration, many of the previous work adopted exploration bonus. The most
commonly used exploration bonus is based on counting. That is, for each pair
$(s,a)$, maintain a integer value $n_{t}(s,a)$ that indicates how many times
the agent performed action $a$ at state $s$ so far at time $t$. Counter-based
methods have been widely used both in practice and in theory (Strehl &
Littman, 2005, 2008; Kolter & Ng, 2009; Bellemare et al., 2016; Tang et al.,
2017; Ostrovski et al., 2017). However, the limitation of these methods still
exist in that the exploratory value of a state-action pair is evaluated with
respect only to its immediate outcome, one step ahead (Choshen et al., 2018).
Recent work (Choshen et al., 2018) proposes an exploration method for model-
free RL that generalizes the counter-based exploration bonus methods and takes
into account long term exploratory value of actions rather than a single step
look-ahead. Inspired by their use of propagated exploration value, we propose
a model-free RL method that utilizes this long-term exploration bonus with
provable efficiency. We show that our proposed method finds a near-optimal
policy in polynomial time, and give experimental evidence that it is an
efficient exploration method.

##  2 Preliminaries

###  2.1 Markov decision processes

A standard assumption of RL is that the environment is (discounted-reward and
finite) Markov decision processes (MDP). Here we only introduce the notational
framework used in this work. A finite MDP $M$ is a tuple
$(\mathcal{S},\mathcal{A},T,R,\gamma)$, where $\mathcal{S}$ is a finite set of
states; $\mathcal{A}$ is a finite set of possible actions;
$T:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}_{S}$ is the transition
distribution; $R:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}_{R}$ is
the reward distribution; $\gamma$ is a discount factor with $\gamma\in[0,1)$.
We assume that all the (random) immediate rewards are nonnegative and are
upper-bounded by a constant $R_{\text{max}}\geq 0$. A policy $\pi$ is a
mapping that assigns to every history $h$ a probability mass function over the
actions $\mathcal{A}$. Following a policy in the MDP means that
$a_{t}\sim\pi(\cdot|h_{t})$. A stationary policy is a mapping
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$. The discounted state- and
action-value functions will be denoted by $V^{\pi}$ and $Q^{\pi}$,
respectively, for any (not necessarily stationary) policy $\pi$. The optimal
state- and action-value functions will be denoted by $V^{*}$ and $Q^{*}$.

Given $s_{0},a_{0},r_{0},s_{1},a_{1},r_{1},...$ a stream of experience
generated when algorithm $\mathfrak{A}$ interacts with $M$, we define its
value at time $t$, conditioned on the past $h_{t}$ as
$V^{\mathfrak{A_{t}}}_{M}=\mathbb{E}[\sum^{\infty}_{k=0}\gamma^{k}r_{t+k}|h_{t}]$.
Let $V_{\textnormal{max}}$ be an upper bound on the state values in the MDP.

###  2.2 Sample Complexity

One of the common evaluation criteria for RL algorithms is to count the number
of non-optimal actions taken. Roughly, this quantity tells how many mistakes
the agent make at most.

######  Definition 1 (Kakade 2003).

Let $\epsilon>0$ be a prescribed accuracy and $\delta>0$ be an allowed
probability of failure. The expression
$\zeta(\epsilon,\delta,S,A,\gamma,R_{\textnormal{max}})$ is a sample
complexity bound for algorithm $\mathfrak{A}$, if the following holds: Take
any $\epsilon>0$, $\delta\in(0,1)$, $S>0$, $A>0$, $\gamma\in[0,1)$,
$R_{\textnormal{max}}>0$ and any MDP $M$ with $S$ states, $A$ actions,
discount factor $\gamma$, and rewards bounded by $R_{\textnormal{max}}$. Let
$\mathfrak{A}$ interact with $M$, resulting in the process
$s_{0},a_{0},r_{0},s_{1},a_{1},r_{1},...$ Then, independently of the choice of
$s_{0}$, with probability at least $1-\delta$, the number of timesteps such
that $V^{\mathfrak{A_{t}}}_{M}<V^{*}_{M}(s_{t})-\epsilon$ is at most
$\zeta(\epsilon,\delta,S,A,\gamma,R_{\textnormal{max}})$.

An algorithm with sample complexity that is polynomial in
$1/\epsilon,\log(1/\delta),S,A,1/(1-\gamma),R_{\textnormal{max}}$ is called
PAC-MDP (probably approximately correct in MDPs)

###  2.3 Previous sample complexity results

$E^{3}$ algorithm (Kearns & Singh, 2002) and its successor, R-max (Brafman &
Tennenholtz, 2002), were the first algorithms that have polynomial time bounds
for finding near-optimal policies. These methods maintain a complete, but
possibly inaccurate model of its environment and acts based on the optimal
policy derived from this model. The model is initialized in an optimistic
fashion: all actions in all states return the maximal possible reward and the
model is updated each time when a state becomes known. R-max has the sample
complexity of
$\widetilde{O}\left(\frac{S^{2}A}{\epsilon^{3}(1-\gamma)^{6}}\right)$. The
MBIE algorithm (Strehl & Littman, 2005, 2008) applies confidence bounds to
compute an optimistic policy and has the same sample complexity
$\widetilde{O}\left(\frac{S^{2}A}{\epsilon^{3}(1-\gamma)^{6}}\right)$. There
are variants of R-max algorithms, such as the OIM algorithm (Szita & Lőrincz,
2008) and MoRMax (Szita & Szepesvári, 2010). MoRMax is shown to have the
smallest sample-complexity
$\widetilde{O}\left(\frac{SA}{\epsilon^{2}(1-\gamma)^{6}}\right)$ among
discounted finite MDPs. All of these algorithms mentioned are model-based.
Unlike aforementioned methods which build an approximate model of the
environment, Delayed Q-learning (Strehl et al., 2006) rather approximate an
action value function directly. Delayed Q-learning is the first model-free
method with known complexity bounds with
$\widetilde{O}\left(\frac{SA}{\epsilon^{4}(1-\gamma)^{8}}\right)$ sample-
complexity.

###  2.4 $E$-values

Choshen et al. (2018) propose a method using a parallel $E$-value MDP which
has the same transition model as the original MDP, but has no rewards
associated with any of the state-actions. Hence, the true value of all state-
action pairs is 0. With the initial value of 1 for all state-action pairs,
they show (empirically) that these $E$-values represent the missing knowledge
and thus can be used for propagating directed exploration. Intuitively, the
value of $E(s,a)$ at a given timestep during training stands for uncertainty
and decreases each time the agents experiences $(s,a)$ pair. On-policy SARSA
(Singh et al., 2000) update rule is applied to the $E$-value MDP, where the
acting policy is selected on the original MDP.

$\vspace{-0.1cm}E(s_{t},a_{t})\leftarrow(1-\alpha)E(s_{t},a_{t})+\alpha\gamma_{E}E(s_{t+1},a_{t+1})$

While the $E$-value MDP is training, the proposed method uses a log
transformation applied to $E$-values to get the corresponding exploration
bonus term for the original MDP. This bonus term is shown to be equivalent
counter-based methods for finite MDPs when the discount factor $\gamma_{E}$ of
the $E$-value MDP is set to 0 if a fixed learning rate $\alpha$ is used for
all updates. Hence, Choshen et al. (2018) argue that, with $\gamma_{E}>0$, the
logarithm of $E$-Values can be thought of as a generalization of visit
counters, with propagation of the values along state-action pairs. Although
the empirical results demonstrate efficient exploration in the experiments
used in their work, the theoretical analysis of their proposed algorithm is
lacking, essentially only showing convergence with infinite visiting. In this
work, we show that $E$-value can be incorporated in PAC-MDP with theoretical
guarantee.

###  2.5 Delayed Q-learning

In Delayed Q-learning (Strehl et al., 2006, 2009), the agent only observes one
sample transition for the action it takes in the current state. Delayed
Q-learning uses optimistic initialization of the value function, and waits
until $m$ transitions from $(s,a)$ are gathered before considering an update
of $Q(s,a)$ (this is where “delay” comes from). When $m$ is sufficiently large
(but is still bounded by a polynomial), the new value of $Q(s,a)$ is still
optimistic with high probability (Li, 2009). It maintains the known state-
action set $K_{t}$, similar to the approaches introduced in earlier model-
based PAC-MDP algorithms (Brafman & Tennenholtz, 2002) as well as Boolean
$LEARN$ flags for each state-action pair that is set as TRUE when a pair does
not belong to the set $K_{t}$, which allows an update to $Q(s,a)$. These tools
allow us to bound the number of occurrence of the undesired “escape” events
from $K_{t}$. A variant of Delayed Q-learning uses techniques such as interval
estimation to attempt an update before $m$-th time as long as the current
estimate satisfies the update criterion (Strehl, 2007).

##  3 Directed Delayed Q-learning

Our proposed algorithm, Directed Delayed Q-learning, maintains Q-value
estimates, $Q(s,a)$ and $E$-value estimates, $E(s,a)$ for each state-action
pair $(s,a)$. At each timestep $t$, let $Q_{t}(s,a)$ denote the algorithm’s
current Q-value estimate and $E_{t}(s,a)$ denote its current $E$-value
estimate. The agent always acts greedily with respect to Q-value estimates
plus the exploration bonus, meaning that if state $s$ is the $t$-th state
reached, the next action is chosen by

$a:=\arg\max_{a\in\mathcal{A}}Q_{t}(s,a)+\frac{\lambda}{\sqrt{\log_{\eta}E_{t}(s,a)}}.$
(1)

Let $Q^{\prime}_{t}(s,a)$ denote
$Q_{t}(s,a)+\lambda/\sqrt{\log_{\eta}E_{t}(s,a)}$ for convenience. Our
proposed method is based on Delayed Q-learning (Strehl et al., 2006, 2009).
Our proposed method modifies Delayed Q-learning in that we introduce an
exploration bonus using $E$-values to take into account the long term
exploratory value of actions and we perform delayed updates to $E$-values
along with Q-values. We also adopt the interval estimation technique (Strehl,
2007) to update the value function whenever a current Monte Carlo estimate
differs from the target value function sufficiently, instead of waiting until
the agent collects a fixed number of $m$ samples to estimate a new value
function for each attempted update. The term $\rho/\sqrt{n(s,a)}$ is
introduced to account for Monte Carlo estimate errors in the case of a
premature delay, where $n(s,a)$ is the inner counter of state-action pairs
within each update and resets after a successful update or the $m$-th
attempted update. Note that $n(s,a)$ differs from a global counter which keeps
track of the number of state-action visits for the entire duration of learning
and which is generalized by $E$-values. It is also important to note that the
proposed $E$-value based exploration bonus can still be applied to the fully
delayed version of Delayed Q-learning with fixed delay intervals (in fact,
with the same PAC bound). We apply the interval estimation technique for
empirical performance gains.

Furthermore, there are differences between our proposed method and Choshen et
al. (2018) in that Choshen et al. (2018) still apply dithering strategies
($\epsilon$-greedy and softmax policies) over the sum of Q-value and a
exploration bonus based $E$-value. On the other hand, our proposed algorithm
acts greedily with respect to Equation (1). We also update $E$-values with
off-policy updates rather than on-policy to ensure monotonic decrease in $E$
value for every update.

In addition to Q-value and $E$-value estimates, similarly to Delayed
Q-learning, our algorithm maintains a Boolean variable $LEARN(s,a)$, for each
$(s,a)$.111The maintenance of the $LEARN(s,a)$ variable is essentially the
same as Delayed Q-learning. For details, see (Strehl et al., 2006, 2009). This
variable indicates whether the agent currently considers a modification to its
Q-value and $E$-value estimates. The algorithm also relies on other free
parameters, $\epsilon_{1}\in(0,1)$ and a positive integer $m$, a positive real
number $\lambda$, $E$-value discount factor $\gamma_{E}$, and the base of log
transformation $\eta$. In the analysis which is provided in Appendix, we
provide precise values for these parameters in terms of the other inputs
$(S,A,\epsilon,\delta,\gamma)$ that guarantee the resulting algorithm is PAC-
MDP. We provide an efficient implementation, Algorithm 1, of Directed Delayed
Q-learning.

Algorithm 1 Directed Delayed Q-learning

Input: $\gamma,S,A,\epsilon_{1},m,\lambda,\gamma_{E},\eta$

for all $(s,a)$ do

$Q(s,a)\leftarrow 1/(1-\gamma)$ // Q-value estimate

$E(s,a)\leftarrow 1-\epsilon_{1}$ // exploration value estimate

$\tilde{Q}(s,a)\leftarrow 0$ // inner loop estimate for Q-values

$\tilde{E}(s,a)\leftarrow 0$ // inner loop estimate for $E$-values

$n(s,a)\leftarrow 0$ // inner counter

$b(s,a)\leftarrow 0$ // beginning time of attempted update

$LEARN(s,a)\leftarrow true$ // the LEARN flags

end for

$t^{*}\leftarrow 0$ // time of most recent Q-value change

for $t=1,2,3,...$ do

Let $s$ denote the state at time $t$

Choose action
$a:=\arg\max_{a^{\prime}\in\mathcal{A}}Q(s,a^{\prime})+\frac{\lambda}{\sqrt{\log_{\eta}E(s,a^{\prime})}}$

Observe immediate reward $r$ and next state $s^{\prime}$

if $b(s,a)\leq t^{*}$ then

$LEARN(s,a)\leftarrow true$

end if

if $LEARN(s,a)=true$ then

$n(s,a)\leftarrow n(s,a)+1$

$\alpha\leftarrow\frac{1}{n(s,a)}$

$\tilde{Q}(s,a)\leftarrow(1-\alpha)\tilde{Q}(s,a)+\alpha\left(r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})\right)$

$\tilde{E}(s,a)\leftarrow(1-\alpha)\tilde{E}(s,a)+\alpha\left(\gamma_{E}\max_{a^{\prime}}E(s^{\prime},a^{\prime})\right)$

if

$Q^{\prime}(s,a)-\left(\tilde{Q}(s,a)+\frac{\rho}{\sqrt{n(s,a)}}+\frac{\lambda}{\sqrt{\log_{\eta}\tilde{E}(s,a)}}\right)\geq\epsilon_{1}$

then

$Q(s,a)\leftarrow\tilde{Q}(s,a)+\frac{\rho}{\sqrt{n(s,a)}}$

$E(s,a)\leftarrow\tilde{E}(s,a)$

$t^{*}\leftarrow t$

$n(s,a)\leftarrow 0;\tilde{Q}(s,a)\leftarrow 0;\tilde{E}(s,a)\leftarrow
0;b(s,a)\leftarrow t$

else if $n(s,a)=m$ then

$n(s,a)\leftarrow 0;\tilde{Q}(s,a)\leftarrow 0;,\tilde{E}(s,a)\leftarrow
0;b(s,a)\leftarrow t$

if $b(s,a)>t^{*}$ then

$LEARN(s,a)\leftarrow false$

end if

end if

end if

end for

###  3.1 Update Criteria

While the agent considers learning for a given state-action pair $(s,a)$, each
time $(s,a)$ is experienced, the agents updates its surrogate Q-value and
$E$-value estimates, $\tilde{Q}$ and $\tilde{E}$ and attempts an update to the
global Q-value and $E$-value up to $m$. If the update fails even at $m$-th
time, the agent discards the current surrogate estimates and starts collecting
new samples. If successful, the following updates occur:
$Q(s,a)\leftarrow\tilde{Q}(s,a)+\rho/\sqrt{n(s,a)}$ and
$E(s,a)\leftarrow\tilde{E}(s,a)$. To ensure that every successful update
decreases $Q^{\prime}(s,a)$ by at least $\epsilon$, we require the following
condition to be satisfied for an update to occur:
$Q^{\prime}(s,a)-\left(\tilde{Q}(s,a)+\frac{\rho}{\sqrt{n(s,a)}}+\frac{\lambda}{\sqrt{\log_{\eta}\tilde{E}(s,a)}}\right)\geq\epsilon_{1}$

If the above condition does not hold, then there is no update to be performed
for $Q(s,a)$ and $E(s,a)$.

Figure 1: Flow of Q-value and $E$-value updates during execution of Directed
Delayed Q-learning. Delay can be up to $m$ times per each attempted update,
which may or may not succeed

###  3.2 Main Theoretical Result

The main theoretical result, whose proof is provided in Appendix in the
supplementary material, is that the Directed Delayed Q-learning algorithm is
PAC-MDP:

######  Theorem 1.

Let $M$ be any MDP and let $\epsilon$ and $\delta$ be two positive real
numbers. If Directed Delayed Q-learning is executed on MDP $M$, then then the
following holds. Let $\mathfrak{A}_{t}$ denote the policy of Directed Delayed
Q-learning at time $t$ and $s_{t}$ denote the state at time $t$. With
probability at least $1-\delta$, $V^{\mathfrak{A_{t}}}_{M}(s_{t})\geq
V^{*}_{M}(s_{t})-\epsilon$ is true for all but

$O\left(\frac{SA}{\epsilon^{4}(1-\gamma)^{8}}\ln\frac{1}{\delta}\ln\frac{1}{\epsilon(1-\gamma)}\ln\frac{SA}{\delta\epsilon(1-\gamma)}\right)$

timesteps.

##  4 Experiments

To assess the empirical performances of Directed Delayed Q-learning, we
compared its performance to other model-free RL methods as well as different
values of $\gamma_{E}$. Experiments were run on chain MDPs with varying length
$N$. The agent begins at the far left state and at every time step has the
choice to move left or right. Each move can fail with probability 0.2, which
results in the opposite action. The agent receives a small reward
$(r=\frac{1}{1000})$ for reaching the leftmost state, but the optimal policy
is to attempt to move to the far right state and receive a much larger reward
$(r=1)$. Chains with length $N=10$ and $N=50$ are reported below. These
environments are intended to be expository rather than entirely realistic.
Balancing a well known and mildly successful strategy versus an unknown, but
potentially more rewarding, approach can emerge in many practical applications
(Osband et al., 2016).

Table 1: Results on Chain MDPs with $N=10$ Method |  | Cumulative reward
---|---|---
Directed Delayed QL | $\gamma_{E}=0.99$ | 7089.59$\pm$48.98
$\gamma_{E}=0.90$ |  6961.50$\pm$63.63
$\gamma_{E}=0.75$ |  4530.78$\pm$94.03
$\gamma_{E}=0.50$ |  2746.06$\pm$61.84
$\gamma_{E}=0.25$ |  2624.71$\pm$14.97
Delayed QL |  |  4325.38$\pm$59.31
QL + $\epsilon$-greedy |  |  2435.11$\pm$134.3
Table 2: Results on Chain MDPs with $N=50$ Method |  | Cumulative reward
---|---|---
Directed Delayed QL | $\gamma_{E}=0.99$ | 5581.02$\pm$94.72
$\gamma_{E}=0.90$ |  4982.09$\pm$116.2
$\gamma_{E}=0.75$ |  2976.96$\pm$282.9
$\gamma_{E}=0.50$ |  707.18$\pm$24.63
$\gamma_{E}=0.25$ |  691.33$\pm$13.60
Delayed QL |  |  531.95$\pm$58.66
QL + $\epsilon$-greedy |  |  2.98$\pm$0.012

On all experiments, each algorithm ran for 10,000 timesteps and the
undiscounted total sum of reward was recorded. Tables 1 and 2 show the average
and 95% confidence intervals over 300 independent test runs. The results show
that Directed Delayed Q-learning significantly outperforms other model-free
methods. Especially, we notice the gap between the performances of the
algorithms increases exponentially as the chain length $N$ increases, which
suggests that the larger value of $\gamma_{E}$ is beneficial especially in
environments where reward is more sparse and deeper exploration is required.

##  5 Conclusion

We presented Directed Delayed Q-learning, a provably efficient model-free
reinforcement-learning algorithm which takes into account long term
exploratory information. It has the same desirable sample complexity as
Delayed Q-learning. The experiments show that Directed Delayed Q-learning
shows significantly better performance compared to other model-free RL methods
on challenging environments.

## References

  * Bellemare et al. (2016) Bellemare, Marc, Srinivasan, Sriram, Ostrovski, Georg, Schaul, Tom, Saxton, David, and Munos, Remi.  Unifying count-based exploration and intrinsic motivation.  In _Advances in Neural Information Processing Systems_ , pp. 1471–1479, 2016.
  * Brafman & Tennenholtz (2002) Brafman, Ronen I and Tennenholtz, Moshe.  R-max-a general polynomial time algorithm for near-optimal reinforcement learning.  _Journal of Machine Learning Research_ , 3(Oct):213–231, 2002.
  * Choshen et al. (2018) Choshen, Leshem, Fox, Lior, and Loewenstein, Yonatan.  Dora the explorer: Directed outreaching reinforcement action-selection.  In _International Conference on Learning Representations_ , 2018.
  * Kakade (2003) Kakade, Sham Machandranath.  _On the sample complexity of reinforcement learning_.  PhD thesis, University College London, 2003.
  * Kearns & Singh (2002) Kearns, Michael and Singh, Satinder.  Near-optimal reinforcement learning in polynomial time.  _Machine learning_ , 49(2-3):209–232, 2002.
  * Kolter & Ng (2009) Kolter, J Zico and Ng, Andrew Y.  Near-bayesian exploration in polynomial time.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , pp. 513–520. ACM, 2009.
  * Li (2009) Li, Lihong.  _A unifying framework for computational reinforcement learning theory_.  Rutgers The State University of New Jersey-New Brunswick, 2009.
  * Little & Sommer (2013) Little, Daniel Ying-Jeh and Sommer, Friedrich Tobias.  Learning and exploration in action-perception loops.  _Frontiers in neural circuits_ , 7:37, 2013.
  * Osband et al. (2016) Osband, Ian, Van Roy, Benjamin, and Wen, Zheng.  Generalization and exploration via randomized value functions.  In _International Conference on Machine Learning_ , pp. 2377–2386, 2016.
  * Ostrovski et al. (2017) Ostrovski, Georg, Bellemare, Marc G, Oord, Aaron van den, and Munos, Rémi.  Count-based exploration with neural density models.  _arXiv preprint arXiv:1703.01310_ , 2017.
  * Singh et al. (2000) Singh, Satinder, Jaakkola, Tommi, Littman, Michael L, and Szepesvári, Csaba.  Convergence results for single-step on-policy reinforcement-learning algorithms.  _Machine learning_ , 38(3):287–308, 2000.
  * Strehl (2007) Strehl, Alexander L.  _Probably approximately correct (PAC) exploration in reinforcement learning_.  PhD thesis, Rutgers University-Graduate School-New Brunswick, 2007.
  * Strehl & Littman (2005) Strehl, Alexander L and Littman, Michael L.  A theoretical analysis of model-based interval estimation.  In _Proceedings of the 22nd international conference on Machine learning_ , pp. 856–863. ACM, 2005.
  * Strehl & Littman (2008) Strehl, Alexander L and Littman, Michael L.  An analysis of model-based interval estimation for markov decision processes.  _Journal of Computer and System Sciences_ , 74(8):1309–1331, 2008.
  * Strehl et al. (2006) Strehl, Alexander L, Li, Lihong, Wiewiora, Eric, Langford, John, and Littman, Michael L.  Pac model-free reinforcement learning.  In _Proceedings of the 23rd international conference on Machine learning_ , pp. 881–888. ACM, 2006.
  * Strehl et al. (2009) Strehl, Alexander L, Li, Lihong, and Littman, Michael L.  Reinforcement learning in finite mdps: Pac analysis.  _Journal of Machine Learning Research_ , 10(Nov):2413–2444, 2009.
  * Szita & Lőrincz (2008) Szita, István and Lőrincz, András.  The many faces of optimism: a unifying approach.  In _Proceedings of the 25th international conference on Machine learning_ , pp. 1048–1055. ACM, 2008.
  * Szita & Szepesvári (2010) Szita, István and Szepesvári, Csaba.  Model-based reinforcement learning with nearly tight exploration complexity bounds.  In _Proceedings of the 27th International Conference on Machine Learning (ICML-10)_ , pp. 1031–1038, 2010.
  * Tang et al. (2017) Tang, Haoran, Houthooft, Rein, Foote, Davis, Stooke, Adam, Chen, OpenAI Xi, Duan, Yan, Schulman, John, DeTurck, Filip, and Abbeel, Pieter.  # exploration: A study of count-based exploration for deep reinforcement learning.  In _Advances in Neural Information Processing Systems_ , pp. 2750–2759, 2017.
  * Thrun (1992) Thrun, Sebastian B.  Efficient exploration in reinforcement learning.  Technical report, Carnegie-Mellon University, 1992.

##  Appendix A Analysis

In this section, we show the proof of the main theoretical result, Theorem 1.
The proofs follow the structure of the work of (Strehl et al., 2009), but
specify some of steps for our proposed method. The following theorem (Theorem
10 in Strehl et al. 2009) will come in handy to show that our proposed
algorithm is PAC-MDP.

######  Theorem 2 (Strehl et al. 2009).

Let $\mathfrak{A}(\epsilon,\delta)$ be any greedy learning algorithm such
that, for every timestep $t$, there exists a set $K_{t}$ of state-action pairs
that depends only on the agent’s history up to timestep $t$. We assume that
$K_{t}=K_{t+1}$ unless, during timestep $t$, an update to some state-action
value occurs or the escape event $A_{K}$ happens. Let $M_{k}$ be the known
state-action MDP and $\pi_{t}$ be the current greedy policy, that is, for all
states $s$, $\pi_{t}(s)=\arg\max_{a}Q^{\prime}_{t}(s,a)$. Furthermore, assume
$Q^{\prime}_{t}(s,a)\leq V^{\prime}_{\textnormal{max}}$ for all $t$ and
$(s,a)$. Suppose that for any inputs $\epsilon$ and $\delta$, with probability
at least $1-\delta$, the following conditions hold for all states $s$, actions
$a$, and timesteps $t$: (a) $V^{\prime}_{t}(s)\geq V^{*}(s)-\epsilon$
(optimism), (b) $V^{\prime}_{t}(s)-V^{\pi_{t}}_{{M_{K}}_{t}}(s)\leq\epsilon$
(accuracy), and (c) the total number of updates of action-value estimates plus
the number of times the escape event from $K_{t}$, $A_{k}$, can occur is
bounded by $\zeta(\epsilon,\delta)$ (learning complexity). Then, when
$\mathfrak{A}(\epsilon,\delta)$ is executed on any MDP $M$, it will follow a
4$\epsilon$-optimal policy from its current state on all but

$O\left(\frac{V^{\prime}_{\textnormal{max}}\zeta(\epsilon,\delta)}{\epsilon(1-\gamma)}\ln\frac{1}{\delta}\ln\frac{1}{\epsilon(1-\gamma)}\right)$

timesteps, with probability at least $1-2\delta$.

Recall that we define $Q^{\prime}_{t}(s,a)$ to be
$Q_{t}(s,a)+\frac{\lambda}{\sqrt{\log_{\eta}E_{t}(s,a)}}$ for convenience. We
first bound the number of successful updates. Since every successful update of
$Q^{\prime}(s,a)$ results in a decrease of at least $\epsilon_{1}$ and
$Q^{\prime}(s,a)$ is initialized to $1/(1-\gamma)$. We have at most
$\kappa:=\frac{1}{(1-\gamma)\epsilon}$ successful updates of a fixed state-
action pair $(s,a)$. Therefore, the total number of successful updates is at
most $SA\kappa$. So there can be at most $m(1+SA\kappa)$ attempted updates for
each pair $(s,a)$. Hence, there are at most of $SAm(1+SA\kappa)$ total
attempted updates.

Following the construction of the set of the low Bellman error state-action
pairs in Delayed Q-learning (Strehl et al., 2009), during timestep $t$ of
learning, we define $K_{t}$ to be the set of all state-action pairs $(s,a)$
such that:

$Q^{\prime}_{t}(s,a)-\left(R(s,a)+\gamma\sum_{s^{\prime}}T(s^{\prime}|s,a)V_{t}(s^{\prime})\right)\leq
4\epsilon_{1}\>.$ (2)

######  Definition 2.

Define Event A1 to be the event that for all timesteps $t$, if $(s,a)\notin
K_{t_{1}}$ and an attempted update of (s,a) occurs during timestep $t$, then
the update will be successful, where $t_{1}<t_{2}<...<t_{m}=t$ are $m$ last
timesteps during which $(s,a)$ is experienced consecutively.

During any given infinite-length execution of Directed Delayed Q-learning,
when $(s,a)\notin K_{t_{1}}$ as above, our value function estimate
$Q^{\prime}(s,a)$ is very inconsistent with our current value function
estimates. Thus, we would expect our next attempted update to succeed. The
next lemma shows that this update occurs with high probability. The proof of
the lemma follows the structure of the lemma of (Strehl et al., 2009), but
also bound the $E$-value estimates and specify additional parameter values. We
specify a value $m$ and first consider values $m_{1}=\frac{(1+\gamma
V_{\textnormal{max}})^{2}}{2\epsilon_{1}^{2}}\ln\left(\frac{6SA(1+SA\kappa)}{\delta}\right)$
and
$m_{2}=\frac{\gamma_{E}^{2}}{2\epsilon_{1}^{2}}\ln\left(\frac{6SA(1+SA\kappa)}{\delta}\right)$.

######  Lemma 1.

The probability that A1 is violated during execution of Directed Delayed
Q-learning is at most $\delta/3$ with $m=m_{1}$,
$\lambda\leq\epsilon\sqrt{\log_{\eta}\epsilon}$ and
$\rho\leq\epsilon_{1}\sqrt{m}$.

###### Proof.

Fix a state-action pair $(s,a)$ and suppose that it has been visited $m$ times
until timestep $t$, at steps $t_{1},...,t_{k}$. Consider $m$ rewards,
$r_{t_{1}},...,r_{t_{m}}$, and $m$ next states, $s_{t_{1}},...,s_{t_{m}}$ for
$(s,a)$. Define the random variables $X_{i}:=r_{t_{i}}+\gamma
V_{t_{1}}(s_{t_{i}})$. Clearly, $0\leq X_{i}\leq(1+\gamma
V_{\textnormal{max}})$. Using the Hoeffding bound with the choice of $m_{1}$
above, it can be shown that

$\frac{1}{m_{1}}\sum_{i=1}^{m_{1}}(r_{t_{i}}+\gamma
V_{t_{1}}(s_{t_{i}}))-\mathbb{E}[X_{1}]<\epsilon_{1}$ (3)

holds with probability at least $1-\delta/(6SA(1+\kappa))$. Similarly, define
the random variable $Y_{i}:=\gamma_{E}G_{t_{1}}(s_{t_{i}})$ where
$G(s)=\max_{a}E(s,a)$. Note that $0\leq Y_{i}\leq\gamma_{E}$. Again, using the
Hoeffding bound with the choice of $m_{2}$ above, it can be shown that

$\frac{1}{m_{2}}\sum_{i=1}^{m_{2}}\gamma_{E}G_{t_{1}}(s_{t_{i}})-\mathbb{E}[Y_{1}]<\epsilon_{1}$
(4)

holds with probability at least $1-\delta/(6SA(1+\kappa))$. Note that given
$\epsilon_{1}<0.5$, we can choose the constants $\eta\in(0,1)$ and
$\lambda\leq\epsilon_{1}\sqrt{\log_{\eta}\epsilon_{1}}$ such that
$E(s,a)\leq\epsilon_{1}$ implies
$\frac{\lambda}{\sqrt{\log_{\eta}E(s,a)}}\leq\epsilon_{1}$. Here we choose
$\eta=1-{\epsilon_{1}}$ (this choice will be useful when we bound
$Q^{\prime}$)

We choose $m\geq m_{1}=\max(m_{1},m_{2})$ since $(1+\gamma
V_{\textnormal{max}})^{2}>\gamma_{E}^{2}$. Hence, it does not matter what
value $\gamma_{E}$ is (as long as $\gamma_{E}\in(0,1)$) to determine the PAC-
bound. We show that if an attempted update is performed for $(s,a)$ using
these $m$ samples, then the resulting update will succeed with high
probability.

$\displaystyle
Q^{\prime}_{t}(s,a)-\left(\frac{1}{m}\sum_{i=1}^{m}(r_{t_{i}}+\gamma
V_{t_{i}}(s_{t_{i}}))+\frac{\rho}{\sqrt{m}}+\frac{\lambda}{\sqrt{\log_{\eta}\frac{1}{m}\sum_{i=1}^{m}\gamma_{E}G_{t_{i}}(s_{t_{i}})}}\right)$
$\displaystyle\geq
Q^{\prime}_{t}(s,a)-\left(\frac{1}{m}\sum_{i=1}^{m}(r_{t_{i}}+\gamma
V_{t_{1}}(s_{t_{i}}))+\frac{\rho}{\sqrt{m}}+\frac{\lambda}{\sqrt{\log_{\eta}\frac{1}{m}\sum_{i=1}^{m}\gamma_{E}G_{t_{1}}(s_{t_{i}})}}\right)$
$\displaystyle>Q^{\prime}_{t}(s,a)-\mathbb{E}[X_{1}]-\epsilon_{1}-\frac{\rho}{\sqrt{m}}-\frac{\lambda}{\sqrt{\log_{\eta}\mathbb{E}[Y_{1}]}}-\epsilon_{1}$
$\displaystyle\geq 4\epsilon_{1}-\frac{\rho}{\sqrt{m}}-2\epsilon_{1}$
$\displaystyle\geq 2\epsilon_{1}-\frac{\rho}{\sqrt{m}}.$

The first inequality follows from $V_{t_{i}}(s)\leq V_{t_{1}}(s)$ and
$G_{t_{i}}(s)\leq G_{t_{1}}(s)$ for all $s$ and $i$. The second inequality
follows from (3) and (4) along with a suitable choice of $\lambda$. The third
step uses the assumption on A1, i.e. $(s,a)\notin K_{t_{1}}$, therefore (2)
doesn’t hold. Hence, if we choose $\rho\leq\epsilon_{1}\sqrt{m}$, then with
probability at least $1-3\delta$ we have:

$Q^{\prime}_{t}(s,a)-\left(\tilde{Q}(s,a)+\frac{\rho}{\sqrt{n(s,a)}}+\frac{\lambda}{\sqrt{\log_{\eta}\tilde{E}(s,a)}}\right)\geq\epsilon_{1}\>.$
(5)

∎

The following lemma states that our proposed algorithm will maintain
optimistic action values with high probability.

######  Lemma 2.

During execution of Directed Delayed Q-learning, $Q_{t}^{\prime}(s,a)\geq
Q^{*}(s,a)$ holds for all timesteps $t$ and state-action pairs $(s,a)$, with
probability at least $1-\delta/3$.

###### Proof.

Fix a state-action pair $(s,a)$ and suppose that it has been visited $k\leq m$
times until timestep $t$, at steps $t_{1},...,t_{k}$. Define the random
variables $X_{1},...,X_{k}$ by $X_{i}:=r_{t_{i}}+\gamma V^{*}(s_{t_{i}+1})$
Note that $\mathbb{E}[X_{i}]=Q^{*}(s,a)$ and $0\leq X_{i}\leq 1+\gamma
V_{\textnormal{max}}$ for all $i=1,...,k$ and the sequence $Q^{*}(s,a)-X_{i}$
is a martingale difference sequence. Applying Azuma’s lemma, we have

$P\left[\mathbb{E}[X_{1}]-\frac{1}{k}\sum_{i=1}^{k}X_{i}\geq\frac{\rho}{\sqrt{k}}\right]\leq\exp\left(-\frac{\rho^{2}}{2(1+\gamma
V_{\textnormal{max}})^{2}}\right).$ (6)

Let the right-hand side be equal to $\frac{\delta}{3SAm(1+SA\kappa)}$. Then
with $\rho\geq\left(1+\gamma
V_{\textnormal{max}}\right)\sqrt{\frac{1}{2}\ln\frac{3SAm(1+SA\kappa)}{\delta}}$,
we have that

$\frac{1}{k}\sum_{i=1}^{k}(r_{t_{i}}+\gamma
V^{*}(s_{t_{i}+1}))+\frac{\rho}{\sqrt{k}}\geq Q^{*}(s,a)$ (7)

holds for all attempted updates, with probability at least $1-3\delta$.
Assuming this equation does hold, the proof of the lemma is by induction on
the timestep $t$. Note that since $Q^{\prime}_{t}(s,a)\geq Q_{t}(s,a)$ for all
$(s,a)$ and $t$, it suffices to show $Q_{t}(s,a)\geq Q^{*}(s,a)$ for all $t$.
For the base case, note that $Q_{1}(s,a)=1/(1-\gamma)\geq Q^{*}(s,a)$ for all
$(s,a)$. Now, suppose that $Q_{t^{\prime}}(s,a)\geq Q^{*}(s,a)$ holds true for
all $t^{\prime}\leq t$. Hence, $Q_{t}(s,a)\geq Q^{*}(s,a)$ and $V_{t}(s)\geq
V^{*}(s)$ for all $(s,a)$. Then we have
$Q_{t+1}(s,a)=\frac{1}{k}\sum_{i=1}^{k}(r_{t_{i}}+\gamma
V_{t_{i}}(s_{t_{i}+1}))+\frac{\rho}{\sqrt{k}}\geq\frac{1}{k}\sum_{i=1}^{k}(r_{t_{i}}+\gamma
V^{*}(s_{t_{i}+1}))+\frac{\rho}{\sqrt{k}}\geq Q^{*}(s,a)$. ∎

######  Lemma 3 (Strehl et al. 2009).

The number of timesteps $t$ such that a state-action pair $(s,a)\notin K_{t}$
is experienced is at most $2mSA\kappa$.

###### Proof.

See Lemma 25 in (Strehl et al., 2009) for proof. Note that although the
proposed algorithm can update Q-value and $E$-values estimates before $m$
attempts. it can take up to $m$ attempts (and still not succeed) in the worst
case. Therefore, the analysis for this lemma is the same as (Strehl et al.,
2009) ∎

Next, we bound $Q^{\prime}(s,a)$ for all state-action pair.

######  Lemma 4.

If $\eta=1-\epsilon_{1}$ and
$\lambda\leq\epsilon_{1}\sqrt{\log_{\eta}\epsilon_{1}}$, then
$Q^{\prime}_{t}(s,a)\leq V_{\textnormal{max}}+\sqrt{1-\epsilon}$ for all $t$
and $(s,a)$.

###### Proof.

Since $E_{0}(s,a)=1-\epsilon$, and $E_{t}(s,a)\leq E_{0}(s,a)$, we have

$\displaystyle Q^{\prime}_{t}(s,a)$
$\displaystyle=Q_{t}(s,a)+\frac{\lambda}{\sqrt{\log_{\eta}E_{t}(s,a)}}$
$\displaystyle\leq
V_{\textnormal{max}}+\epsilon_{1}\sqrt{\log_{\eta}\epsilon_{1}}=V_{\textnormal{max}}+\epsilon_{1}\sqrt{\frac{\log\epsilon_{1}}{\log(1-\epsilon_{1})}}$
$\displaystyle\leq
V_{\textnormal{max}}+\epsilon_{1}\sqrt{\frac{\frac{1}{\epsilon_{1}}-1}{\epsilon_{1}}}=V_{\textnormal{max}}+\sqrt{1-\epsilon}$

∎

Using these Lemmas we can prove the main result, Theorem 1.

###### Proof.

(of Theorem 1) We show that combining Lemmas satisfies the conditions of
Theorem 2. First, set $m$ as in Lemma 1 and let
$\epsilon_{1}=\epsilon(1-\gamma)/4,\eta=1-\epsilon_{1},\rho=\epsilon_{1}\sqrt{m}$
and $\lambda=\epsilon_{1}\sqrt{\log_{\eta}\epsilon_{1}}$. Let
$V^{\prime}_{\textnormal{max}}=V_{\textnormal{max}}+\sqrt{1-\epsilon}$. Then,
by Lemma 4, $Q^{\prime}_{t}(s,a)\leq V^{\prime}_{\textnormal{max}}$ for all
$t$ and $(s,a)$. By Lemma 1, event A1 holds with probablity at least
$1-\delta/3$. Then, the optimism condition (a) $V^{\prime}_{t}(s)\geq
V^{*}(s)-\epsilon$ is satisfied by Lemma 2. Note that for all $(s,a)$ if
$(s,a)\in K_{t}$, then equation (1) holds. Otherwise
$Q^{\prime}_{t}(s,a)=Q^{\pi_{t}}_{M_{K_{t}}}(s,a)$. Hence,
$V^{\prime}_{t}(s,a)$ and $V^{\pi_{t}}_{M_{K_{t}}}(s,a)$ can be off by at most
$4\epsilon$ in reward at each time $t$. Therefore,
$V^{\prime}_{t}(s,a)-V^{\pi_{t}}_{M_{K_{t}}}(s,a)\leq\frac{4\epsilon_{1}}{1-\gamma}=\epsilon$,
which satisfies condition (b); see, e.g. (Strehl et al., 2009). Now, from
Lemma 3, we have $\zeta(\epsilon,\delta)=2mSA\kappa$, where
$\zeta(\epsilon,\delta)$ is the number of updates and escape events that occur
during execution of Directed Delayed Q-learning. Hence, putting the results
together, the algorithm will follow a $\epsilon$-optimal policy from its
current state on all but

$O\left(\frac{SA}{\epsilon^{4}(1-\gamma)^{8}}\ln\frac{1}{\delta}\ln\frac{1}{\epsilon(1-\gamma)}\ln\frac{SA}{\delta\epsilon(1-\gamma)}\right)$

timesteps. ∎


MIQP and Iterative Clustering for Semi-Supervised SVMs]
Mixed-Integer Quadratic Optimization
and Iterative Clustering
Techniques for
Semi-Supervised Support Vector Machines

J. P. Burgard, M. E. Pinheiro, M. Schmidt]
Jan Pablo Burgard, Maria Eduarda Pinheiro, Martin Schmidt

[J. P. Burgard]
Trier University,
Department of Economic and Social Statistics,
Universitätsring 15,
54296 Trier,

[M. E. Pinheiro, M. Schmidt]
Trier University,
Department of Mathematics,
Universitätsring 15,
54296 Trier,

Among the most famous algorithms for solving classification problems are
support vector machines (SVMs), which find a separating hyperplane for
a set of labeled data points.
In some applications, however, labels are only available for a subset
of points.
Furthermore, this subset can be non-representative, e.g., due to
self-selection in a survey.
Semi-supervised SVMs tackle the setting of labeled and
unlabeled data and can often improve the reliability of the
results. Moreover, additional information about the size of the
classes can be available from undisclosed sources. We propose a
mixed-integer quadratic optimization (MIQP) model that covers the
setting of labeled and unlabeled data points as well as the overall
number of points in each class. Since the MIQP's solution time
rapidly grows as the number of variables increases, we introduce
an iterative clustering approach to reduce the model's size.
Moreover, we present an update rule for the required big-$M$
values, prove the correctness of the iterative clustering method as
well as derive tailored dimension-reduction and warm-starting
Our numerical results show that our approach leads to a similar
accuracy and precision than the MIQP formulation but at much lower
computational cost.
Thus, we can solve larger problems.
With respect to the original SVM formulation, we observe that our
approach has even better accuracy and precision for biased samples.

titleSVM-KM: speeding SVMs learning with a priori cluster
selection and k-means
journaltitleProceedings. Vol.1. Sixth Brazilian Symposium on
Neural Networks

titleNP-hardness of Euclidean sum-of-squares clustering
journaltitleMachine Learning

titleManifold regularization: a geometric framework for learning
from labeled and unlabeled examples
journaltitleJournal of Machine Learning Research

MIT Press

booktitleProceedings of the 11th International Conference on
Neural Information Processing Systems
titleSemi-Supervised Support Vector Machines

titleReduction of Training Data for Support Vector Machine: A
Berlin, Heidelberg

journaltitleSoft Computing

Kluwer Academic Publishers

titleCBCH (Clustering-Based Convex Hull) for Reducing Training
Time of Support Vector Machine

journaltitleThe Journal of Supercomputing

ACM Press

booktitleProceedings of the Fifth Annual Workshop on Computational
Learning Theory
seriesCOLT '92
titleA Training Algorithm for Optimal Margin Classifiers
Pittsburgh, Pennsylvania, USA

Bootstrap, Constrained maximum likelihood, Logit scaling, Multinomial
logit, Spatiotemporal modeling
Spatial dynamic microsimulations allow for the multivariate analysis of
complex systems with geographic segmentation. A synthetic replica of the
system is stochastically projected into future periods using micro-level
transition probabilities. These should accurately represent the dynamics of
the system to allow for reliable simulation outcomes. In practice, transition
probabilities are unknown and must be estimated from suitable survey data.
This can be challenging when the dynamics vary locally. Survey data often
lacks in regional detail due to confidentiality restrictions and limited
sampling resources. In that case, transition probability estimates may
misrepresent regional dynamics due to insufficient local observations and
coverage problems. The simulation process subsequently fails to provide an
authentic evolution of the system. A constrained maximum likelihood approach
for probability alignment to solve these issues is proposed. It accounts for
regional heterogeneity in transition dynamics through the consideration of
external benchmarks from administrative records. It is proven that the method
is consistent. A parametric bootstrap for uncertainty estimation is
presented. Simulation experiments are conducted to compare the approach with
an existing method for probability alignment. Furthermore, an empirical
application to labor force estimation based on the German Microcensus is

titleEstimation of regional transition probabilities for spatial
dynamic microsimulations from survey data lacking in regional detail
journaltitleComputational Statistics & Data Analysis

titleSupport Vector Machine Classification Based on Fuzzy
Clustering for Large Data Sets

Association for Computing Machinery

booktitleProceedings of the 23rd International Conference on
Machine Learning
seriesICML '06
titleA Continuation Method for Semi-Supervised SVMs
New York, NY, USA

booktitleProceedings of the Tenth International Workshop on
Artificial Intelligence and Statistics
seriesProceedings of Machine Learning Research
titleSemi-Supervised Classification by Low Density Separation

titleSupport Vector Networks
journaltitleMachine Learning

titleThe hardness of k-means clustering

titleJuMP: A Modeling Language for Mathematical Optimization
journaltitleSIAM Review

American Statistical Association

titleSample Quantiles in Statistical Packages
journaltitleThe American Statistician

Springer US

booktitleLearning to Classify Text Using Support Vector Machines
titleTraining Transductive Support Vector Machines

titleA semi-supervised approach using label propagation to support
citation screening
journaltitleJournal of Biomedical Informatics

titleLeast squares quantization in PCM
journaltitleIEEE transactions on information theory

booktitle5th Berkeley Symp. Math. Statist. Probability
titleClassification and analysis of multivariate observations

titleThe planar k-means problem is NP-hard
journaltitleTheoretical Computer Science

titleLaplacian Support Vector Machines Trained in the Primal
journaltitleJournal of Machine Learning Research

titlePMLB: a large benchmark suite for machine learning evaluation
and comparison
journaltitleBioData Mining

titleInverse probability weighting for clustered nonresponse

Elsevier Ltd

booktitleAASRI Procedia 1
titleA Transductive Support Vector Machine Algorithm Based on
Spectral Clustering

titleK-SVM: An effective SVM algorithm based on K-means
journaltitleJournal of Computers

§ DETAILED INFORMATION ON THE INSTANCES

§ FURTHER NUMERICAL RESULTS

Besides the measures of accuracy and precision, we compare two further
measures in this section.
First, recall ($\RE$) measures the percentage of points with positive
label that are actually classified as positive.
It is formally given by

\begin{equation}
\label{recall}
\RE \define \frac{\TP}{\TP+\FN}.
\end{equation}

Note that for applications such as cancer diagnosis, it is relevant to
evaluate recall because it is more important to flag cancer rather
than to do not.
Also in cases of rare positive labels, recall is often the favored
Note that values close to 1 indicate a better classification here.

Second, we also compare the false positive rate ($\FPR$), which
measures the probability of points with negative labels being
classified as positive:

\begin{equation}
\label{fpr}
\FPR \define \frac{\FP}{\TN+\FP}.
\end{equation}

This quantity is important in some applications such as quality control,
where a false positive can cause more issues than a false negative.
Note that for $\FPR$, the lower the value, the better the

The main comparison in terms of recall and false positive rate is
w.r.t. the “true hyperplane”, i.e., the solution of
Problem (<ref>) on the complete data with all $N$ points and all
labels available.
The main question is how close the recall and false positive rate is
to the one of the true hyperplane.
Hence, we compute the ratios of the recall and false positive rate
according to

\begin{equation}
\label{compartrue2}
\widehat{\RE} \define \frac{\RE}{\RE_{\true}},
\quad
\widehat{\FPR} \define \frac{\FPR}{\FPR_{\true}},
\end{equation}

where $\RE_{\true}$ and $\FPR_{\true}$ are computed as
in (<ref>) and (<ref>) for the true hyperplane.

As can be seen in Figure <ref>, the SVM's relative recall is a
little bit larger than the one of the other methods. As in
Section <ref>, this happens because the biased sample is
more likely to have positive labeled data and having no information about
the unlabeled data, the SVM ends up classifying points on the positive side.

Relative recall $\widehat{\RE}$ w.r.t. the true
hyperplane; see (<ref>).
Left: Comparison for all data points.
Right: Comparison only for unlabeled data points.

Figure <ref> shows that CS$^3$VM, the IRCM, and the WIRCM have
lower $\widehat{\FPR}$ values than the original SVM.
This means that the newly proposed methods have a lower false positive
rate than the original SVM.
The fact that CS$^3$VM terminates for less instances than the
IRCM explains why the IRCM has a lower relative false positive rate
than CS$^3$VM.
Finally, since the WIRCM uses the IRCM for warm-starting, the WIRCM
also has better relative false positive rates than CS$^3$VM.

Relative false positive rate $\widehat{\FPR}$ w.r.t. the true
hyperplane; see (<ref>).
Left: Comparison for all data points.
Right: Comparison only for unlabeled data points.

§ NUMERICAL RESULTS FOR SIMPLE RANDOM SAMPLES

In Section <ref>, we focused our
computational study on non-representative, biased samples.
The common baseline scenario to check the performance of estimators is
to apply them on simple random samples. Hence, for completeness, we
also present the results under simple random sampling. That is, each
unit in the data set has the same probability $\pi_i = n/N$ to be
included into the sample of size $n$.
The instances are the same as described in
Section <ref>.
The computational setup follows the description in
Section <ref>.
As before, the used evaluation criteria are
$\widehat{\AC},$ $\widehat{\PR}$ as in (<ref>)
and $\widehat{\RE},$ $\widehat{\FPR}$ as in (<ref>).

Relative accuracy $\widehat{\AC}$ w.r.t. the true
hyperplane; see (<ref>), for the simple random samples.
Left: Comparison for all data points.
Right: Comparison only for unlabeled data points.

Figure <ref> and <ref> show similar accuracy and
precision performance for all approaches. This is as expected, as the
sample is not biased and hence the cardinality constraint does not
contribute relevant additional information to the problem.
Therefore, the SVM does not tend to classify the points as positive as
it is the case for the biased samples.
The outliers, mainly present for CS$^3$VM, are due those instances
that are not solved within the time limit.
As can be seen in Figure <ref> and <ref>, recall and
false positive rate are also similar for all approaches.

Hence, for the simple random samples our approaches have almost the
same results as the SVM.
Note that for the biased samples, they outperformed the SVM.
Hence, in cases for which the type of sample is not known,
it is “safe” to use the newly proposed approaches for

Relative precision $\widehat{\PR}$ w.r.t. the true
hyperplane; see (<ref>), for the simple random samples.
Left: Comparison for all data points.
Right: Comparison only for unlabeled data points.

Relative recall $\widehat{\RE}$ w.r.t. the true hyperplane;
see (<ref>), for the simple random samples.
Left: Comparison for all data points.
Right: Comparison only for unlabeled data points.

Relative false positive rate $\widehat{\FPR}$ w.r.t. the
true hyperplane; see (<ref>), for the simple random samples.
Left: Comparison for all data points.
Right: Comparison only for unlabeled data points.

§ CHOOSING THE HYPERPARAMETERS

Each parameter of Algorithm <ref> and <ref> as well as in Problem (<ref>) and (<ref>)
can be chosen from a range. In Table <ref> we present
plausible ranges for these parameters.

Plausible ranges for the hyperparameters

Parameter     Plausible Range      Current Choice

$C_1$     $\mathbb{R}_{\geq 0}$     $1$

$C_2$     $[0.5 C_1, 2C_1]$     $1$

$k^1$     $[2,m]$     $10,20,50$

$k^+$     $[k^1,m]$     $50 $

$\hat{\Delta}^1$     $[0.5, 0.9]$     $0.8$

$\tilde{\Delta}$     $[0.1 ,1-\hat{\Delta}^1]$     $0.1$

$B_{\max}$     $[1, m]$     $0.2m,0.25m,0.35m,0.45m$

$\gamma$     $[1.1, m/B_{\max}]$     $1.2$

$T_{\max}$     $[10, 100]s$    $40s$

Clearly, $C_1 \in \mathbb{R}_{\geq 0}$ holds.
However, the closer the value is to 1, the more equally important
are maximizing the margin and minimizing the classification error
for the labeled data. The range of $C_2$ is based on
$C_1$ in order to indicate how much more important the unlabeled
data is compared to the labeled data.
Again, we choose $C_2 = 1$ so that both data have the
same importance. Besides that, if $C_2$ is much bigger than $C_1$,
our preliminary tests showed that this leads to focus on
minimizing the classification error for the unlabeled data, which
implies focusing on the binary variable and, hence, leads to larger
run times.

For choosing the other parameters, we consider the first $3$
datasets presented in Table <ref> and varied the parameter
choices in a preliminary numerical study.
Based on the results, we now discuss how to choose the remaining
The parameter $k^1$ can be between $2$ and $m$ since we
cluster $m$ unlabeled points.
Note that, the smaller $k^1$, the less time per iteration is needed
since we have fewer binary variables.
However, more iterations may be needed to find the solution.
On the other hand, the bigger $k^1$, the more time per iteration is
We choose to start with a small value of $k^1$ because in
preliminary numerical tests, when the algorithm terminated, the
number of clusters never exceeded $m/3$.
Moreover, in our preliminary tests, if the algorithm exceeds
$k^t=50$ for some iteration $t$, it takes a lot of time to solve
Problem (<ref>).
To decrease this time, we reduced the number of clusters,
eliminating the ones being far from the hyperplane.
This is the reason why we choose $k^+ = 50$.

The parameter $\hat{\Delta}^1$ indicates that clusters with a
distance to the hyperplane greater than the
$\hat{\Delta}^1$-quantile of all distances will be deactivated.
It is between $0.5$ and $0.9$ because a smaller value than $0.5$
means removing points that are too close to the hyperplane.
This implies that in next iterations many clusters can be
On the other hand, if it is larger than $0.9$, it means that almost
no clusters can be deactivated.
We choose $0.8$ because in our preliminary numerical
tests we noticed that with a smaller value, many clusters were
activated again, which increased the required time per iteration.
The range of $\tilde{\Delta}$ is justified by the fact that for
all $t$, the maximum value of $\hat{\Delta}^t$ is $1$.
We chose $0.1$ because the higher the value we choose, the smaller the
possibility to eliminate clusters becomes.
If chosen smaller, $\hat{\Delta}^t$ and $\hat{\Delta}^{t+1}$
would be very similar and some clusters would be deactivated and
reactivated several times.

Because we have $m$ unlabeled points, we can fix at most $m$
unlabeled points, which justifies the range of $B_{\max}$ and the
maximum value of $\gamma$.
Since some points are not fixed on some side—they may be on the
wrong side or it could take more than $T_{\max}$ to solve
Problem (<ref>)—we try to fix at least more than
10 of $B_{\max}$ many unlabeled points.
This is why the minimum value of $\gamma$ is 1.1.
The maximum value of $T_{\max}$ is 100 because,
if chosen smaller, we observe that there is often not enough time to
solve Problem (<ref>).
On the other hand, if it is larger, we observe that the time needed
to solve the Algorithm <ref> increases.

§ RUN TIMES IN DEPENDENCE OF THE NUMBER OF DATA POINTS

In this section, we complement
Section <ref> by presenting the run times in
dependence of the number of points in the data set in order to shed
some light on the scalability of our approaches.
To this end, we split the entire data set in three subsets.

ECDFs for run time (in seconds).
Top: Instances with $N \geq 500$.
Middle: Instances with $N \in  (500,1500]$.
Bottom: Instances with $N > 1500$.

The first subset only considers those 46 data sets with $N \leq
As can be seen in Figure <ref> (top), IRCM
solves more than 75 of the instances while CS$^3$VM
and WIRCM solve more than 50.
The second subset contains 11 data sets with $N \in (500,1500]$.
Figure <ref> (middle) shows that for these test sets, IRCM solves
about 40 of the instances while CS$^3$VM and WIRCM
solve more than 10.
The last subset contains those 21 data sets with $N > 1500$.
Figure <ref> (bottom) shows that CS$^3$VM and WIRCM do not solve any of
these instances and IRCM solves about 20.
As expected, the larger the number of points and, thus, the larger
the number of binary variables, the more challenging it is to solve
the instances.
Besides that, SVM solves all instances, which is expected since it
does not include any binary variables.