
\subsection{The ski rental problem}

We provide here a full proof of Theorem \ref{thm:PDLA ski rental main}. In our setting, the prediction $\A$ is the predicted number of skiing days $N^{\textit{pred}}$ and $S(\A,\I)=S(N^{\textit{pred}},\I)=B \cdot \mathbbm{1} \{ N^{\textit{pred}} > B \} + N \cdot \mathbbm{1} \{ N^{\textit{pred}} \leq B \} $ is the cost of following blindly the prediction. We first prove an easy lemma about the feasibility of the dual solution.
\begin{lem}
\label{lem:dual_ski_rental_feasible}
Let $y$ be the dual solution built by Algorithm \ref{alg:PDLA for Ski-Rental}. Then $y$ is a feasible solution (assuming $\frac{B}{\lambda}$ is integral if the prediction suggests to rent).
\end{lem}
\begin{proof}
To see this, note that the only constraint that might by violated is the constraint $\sum_{j\in [N]}y_j \leq B$. Denote by $S$ the value of the sum $\sum_{j\in [N]}y_j$. Note that once $x\geq 1$, the value of $S$ will never change anymore. The value of $S$ increases by $1$ for every big update and by $\lambda$ for every small update. In the case $N^{\textit{pred}}>B$, the algorithm always does big updates (the prediction suggest to buy). We claim that at most $\left\lceil \lambda B\right\rceil$ big updates can be made before $x\geq 1$. We denote $x(k)$ the value of $x$ after $k$ updates. We then prove by induction that $x(k)\geq \frac{e(k/B)-1}{e(\lambda)-1}$ (recall that $e(z) = (1+1/B)^{z \cdot B}\approx e^z$). Clearly, if $k=0$, we have $x(0)\geq 0$. Now assume this is the case for $k$ updates we then have
\begin{align*}
    x(k+1) &= \left(1+\frac{1}{B} \right)\cdot x(k) + \frac{1}{(e(\lambda)-1)\cdot B}\\
    &\geq  \left(1+\frac{1}{B} \right)\cdot \frac{e(k/B)-1}{e(\lambda)-1} + \frac{1}{(e(\lambda)-1)\cdot B}\\
    &= \frac{\left(1+1/B \right)\cdot (e(k/B)-1) + 1/B}{e(\lambda)-1}\\
    &= \frac{e((k+1)/B)-1}{e(\lambda)-1}
\end{align*}
which ends the induction. Hence at most $\left\lceil \lambda B\right\rceil\leq B$ big updates can be made before $x\geq 1$. This implies that $S\leq B$ at the end of the algorithm. In the case where $N^{\textit{pred}} \leq B$, we prove in exactly the same way that at most $\left\lceil \frac{B}{\lambda}\right\rceil$ updates are performed before $x\geq 1$. Hence we have that $S\leq \lambda \cdot \left\lceil \frac{B}{\lambda}\right\rceil$. By assumption, we have that $B/\lambda$ is an integer hence $S\leq 1$ and $y$ is again feasible.
\end{proof}

We can finish the main proof.
\begin{proof}[Proof of Theorem \ref{thm:PDLA ski rental main}]
We prove first the robustness bound. By the Lemma \ref{lem:dual_ski_rental_feasible}, we know that the dual solution is feasible. Hence what remains to prove is to upper bound the ratio $\frac{\Delta P}{\Delta D}$ and use weak duality. In the case of a big update we have 
$$ \frac{\Delta P}{\Delta D} = \Delta P = 1+\frac{1}{e(\lambda)-1}=\frac{1}{1-e(-\lambda)}$$
In the case of a small update we have
$$\frac{\Delta P}{\Delta D} = \frac{\Delta P}{\lambda} = \frac{1}{\lambda} \cdot \frac{1}{1-e(-1/\lambda)}\leq \frac{1}{1-e(-\lambda)}$$
where the last inequality comes from Lemma \ref{lem:inequalities} inequality \eqref{eqn:lemma12_1b}. By weak duality, we have the robustness bound.

To prove consistency, we have two cases. If $N^{\textit{pred}}\leq B$, then Algorithm \ref{alg:PDLA for Ski-Rental} does at most $N$ updates, each of cost at most $\frac{1}{1-e(-1/\lambda)}$ while the prediction $\A$ pays a cost of $N$. Noting again that, by Lemma \ref{lem:inequalities}, $\frac{1}{1-e(-1/\lambda)}\leq \frac{\lambda}{1-e(-\lambda)}$ ends the proof of consistency in this case. The other case is different. As in the proof of Lemma \ref{lem:dual_ski_rental_feasible}, we still have that $x(k)\geq \frac{e(k/B)-1}{e(\lambda)-1}$ hence at most $\left\lceil \lambda B\right\rceil\leq B$ updates are done by Algorithm, each of cost at most $\frac{1}{1-e(-\lambda)}$ hence a total cost of at most 
$$ \frac{\left\lceil \lambda B\right\rceil}{1-e(-\lambda)}$$ 
Since we assume in this case that $\lambda B$ is integral and that the prediction $\A$ pays a cost of $B$, the competitive ratio is indeed $\frac{\lambda}{1-e(-\lambda)}$
\end{proof}

\subsection{The Bahncard problem}

\paragraph{History of the problem.} The Banhcard problem, which was initially introduced in \cite{F01}, models a situation where a tourist travels every day multiple trips. Before any new trip, the tourist has two choices, either to buy a ticket for that particular trip at a cost of $1$ or buy a discount card, at a cost of $B$, and use this discount card to get a ticket for a price of $\beta < 1 $. The discount card is then valid for rest of that day and for the next $T-1$ days. This generalizes the ski rental problem in several ways, first the discount expires after a fixed amount of time, second buying only offers a discount and not a free trip. Note that if ${\beta = 0}$ and ${T \xrightarrow[]{} \infty} $ we recover the ski-rental problem. Karlin et al.  \cite{TCPandOtherStories} designed an optimal randomized online algorithm of competitive ratio $\frac{e}{e-1+\beta}$ when ${B \xrightarrow[]{} \infty}$.  

\paragraph{PDLA for the Bahncard problem.} We design, using PDLA, a learning augmented algorithm for the Bahncard problem. The final goal is to prove Theorem \ref{thm:PDLA bahncard}. An interesting feature of our algorithm is that, as for the TCP ack problem, it does not need to be given the full prediction in advance. If Bahncards are bought by the prediction $\A$ at a set of times $\{t_1, t_2,\ldots, t_k\}$, the algorithm does not need to know before time $t_i$ that the Bahncard $i$ is bought. For instance we could think of the prediction of an employee of the station giving short-term advice to a traveller every time he shows up at the station.

We now give the primal dual formulation of the Bahncard problem along with its corresponding learning augmented algorithm. We mention that, to the best of our knowledge, no online algorithm using the primal-dual method was designed before. Hence the primal-dual formulation (Figure \ref{fig:PD_Bahncard}) of the problem is new. In an integral solution, we would have $x_t=1$ if the solution buys a Bahncard at time $t$ and $x_t=0$ otherwise. Then $f_j$ represents the fractional amount of trip $j$ done at time $t(j)$ that is bought at full price and $d_j$ the amount of the trip bought at discounted price. The first natural constraint is the one that says that each trip should be paid entirely either in discounted or full price, i.e. $d_j+f_j\geq 1$. We then have the constraint $\sum_{t=t(j)-T}^{t(j)} x_t \geq d_j$ that says that to be able to buy a ticket at discounted price, at least one Bahncard must have been bought in the last $T$ time steps. 
\begin{figure}[h]
    \centering
    \caption{Primal Dual formulation of the Bahncard problem.}
    \label{fig:PD_Bahncard}
    \begin{tabular}{|c|c|}
    \hline
    \textbf{Primal} &  \textbf{Dual} \\
    \hline
     \text{minimize} $B \cdot \sum_{t \in T } x_t + \sum_{j \in M }\beta d_j + f_j$  & \text{maximize} $\sum_{j \in M } c_j$ \\
     \text{subject to:} $\quad d_j+f_j \geq 1 \quad \forall j$ & \text{subject to:} $\quad c_j\leq 1 \quad \forall j$ \\
     $\sum_{t=t(j)-T}^{t(j)} x_t \geq d_j \quad \forall j$ & $c_j-b_j\leq \beta \quad \forall j$ \\
     $x_t\geq 0 \quad \forall t\in \mathcal  T$ & $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j \leq B \quad \forall t\in \mathcal T$\\
     $d_j,f_j \geq 0 \quad \forall j$ & $c_j,b_j\geq 0 \quad \forall j$\\
     
     \hline 
\end{tabular}{}
    
\end{figure}{}

Following the same idea as for the ski rental problem, we will guide the updates in the primal-dual algorithm with the advice provided. We define a function $e(z)=\left(1+\frac{1-\beta}{B} \right)^{z\cdot (B/(1-\beta))}$. Again for $\frac{B}{1-\beta}\rightarrow \infty$, the reader should think intuitively of $e(z)$ as $e^z$. The parameter $z$ will then take values either $\lambda$ or $1/\lambda$ depending on if we want to do a big or small update in the primal. As for ski rental, when we do a small update, we will need to scale down the dual update by a factor of $\lambda$ to maintain feasibility of the dual solution.

The rule to decide if an update should be big or small is the following: if the prediction $\mathcal A$ bought a Bahncard less than $T$ time steps in the past (i.e. if the predicted solution has currently a valid Bahncard) the update should be big. Otherwise the update should be cautious. In algorithm \ref{alg:LA Primal-Dual for Bahncard}, we denote by $l_\mathcal{A}(t)$ the latest time before time t at which the prediction $\mathcal{A}$ bought a Bahncard. We use the convention that $l_\mathcal{A}(t)=-\infty$ if no Bahncard was bought before time $t$. Of course in this problem it is possible that trips show up while the fractional solution already has a full Bahncard available (i.e. $\sum_{t=t(j)-T}^{t(j)} x_t\geq 1$). In this case there is no point in buying more fractions of a Bahncard and the algorithm will do what we call a \textit{minimal} update. 

\begin{algorithm}[H]
   \caption{\textsc{LA Online Primal-Dual for the Bahncard problem}}
   \label{alg:LA Primal-Dual for Bahncard}
\begin{algorithmic}
   \STATE {\bfseries Input: $\lambda$, $\mathcal A$}
   \STATE {\bfseries Initialize:} $x,d,f \leftarrow 0$, $c,b\leftarrow 0$
   \FORALL{trip $j$}
        \IF{$\sum_{t=t(j)-T}^{t(j)} x_t \geq 1$}
        \STATE $d_j\leftarrow 1$
        \STATE $c_j\leftarrow \beta$
        \ENDIF
        \IF{$\sum_{t=t(j)-T}^{t(j)} x_t < 1$}
        \IF{$t(j)\leq l_\mathcal{A}(t(j))+T$}
        \STATE $d_j \leftarrow \sum_{t=t(j)-T}^{t(j)} x_t$
        \STATE $f_j \leftarrow 1-d_j$
        \STATE $x_{t(j)} \leftarrow x_{t(j)} + \frac{1-\beta}{B}\cdot \left(\sum_{t=t(j)-T}^{t(j)} x_t + \frac{1}{e(\lambda)-1}\right)$
        \STATE $b_j \leftarrow 1-\beta$
        \STATE $c_j\leftarrow b_j+\beta$
        \ENDIF
        \IF{$t(j)> l_\mathcal{A}(t(j))+T$}
        \STATE $d_j \leftarrow \sum_{t=t(j)-T}^{t(j)} x_t$
        \STATE $f_j \leftarrow 1-d_j$
        \STATE $x_{t(j)} \leftarrow x_{t(j)} + \frac{1-\beta}{B}\cdot \left( \sum_{t=t(j)-T}^{t(j)} x_t + \frac{1}{e(1/\lambda)-1}\right)$
        \STATE $b_j \leftarrow \lambda (1-\beta)$
        \STATE $c_j\leftarrow b_j+\beta$
        \ENDIF
        \ENDIF
   \ENDFOR
\end{algorithmic}
\end{algorithm}

We first prove that the dual built by the algorithm is almost feasible.

\begin{lem}
\label{lem:dual_bahncard}
Let $(c,b)$ be the dual solution built by Algorithm \ref{alg:LA Primal-Dual for Bahncard}, then $\frac{(c,b)}{1+(1-\beta)/B}$ is feasible.
\end{lem}
\begin{proof}
Note that the constraints $c_j\leq 1$ and $c_j-b_j\leq \beta$ are clearly maintained by the algorithm. And scaling down both $c$ and $b$ by some factor bigger than $1$ will not alter their feasibility. Hence we focus only on the constraints of the form $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j \leq B$ for a fixed time $t$. Note that during a minimal update, the value of $b_j$ is not changed hence only small or big updates can alter the value of the sum $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j$. Similarly as for proofs in ski rental, denote by $b$ the number of big updates that are counted in this sum and by $s$ the number of small updates in this sum. 

We first notice that once we have that $\sum_{t'=t}^{t+T} x_{t'} \geq 1$, no updates that alter the constraint $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j$ can happen. To see this, note that upon arrival of a trip $j$ between time $t$ and $t+T$, we have $\sum_{t=t(j)-T}^{t(j)} x_t \geq \sum_{t'=t}^{t(j)} x_{t'}=\sum_{t'=t}^{t+T} x_{t'}$.


Denote by $S$ the value of the sum $\sum_{t'=t}^{t+T} x_{t'}$. Note that for a big update, we have that the value of the sum $S$ is increased to at least $S\cdot \left(1+\frac{1-\beta}{B} \right)+\frac{1-\beta}{B}\cdot \frac{1}{e(\lambda)-1}$. Similarly for a small update the new value of the sum is at least $S\cdot \left(1+\frac{1-\beta}{B} \right)+\frac{1-\beta}{B}\cdot \frac{1}{e(1/\lambda)-1}$. Hence we can apply directly Lemma \ref{lem:sequence_lemma} with $d = \frac{B}{1-\beta}$ to conclude that once $b+\lambda s \geq \frac{B}{1-\beta}$, we have that $S\geq 1$. 

Since for a big update, the sum $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j$ increases by $1-\beta$ and by $\lambda (1-\beta)$ for a small update we can see that the first time the constraint $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j\leq B$ is violated, we have $S\geq 1$. Now since each update in the sum $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j$ is of value at most $1-\beta$ we can conclude that at the end of the algorithm, we have $\sum_{j:t(j)-T\leq  t\leq  t(j)} b_j\leq B+1-\beta$ hence the conclusion. 
\end{proof}

We then prove robustness of Algorithm \ref{alg:LA Primal-Dual for Bahncard} by the following lemma. 

\begin{lem}[Robustness]
\label{lem:robustness Bahncard}
For any $\lambda\in (0,1]$ and any $\beta \in [0,1]$, PDLA for the Bahncard problem is $\frac{\left(e(\lambda)-\beta\right)\cdot \left(1+(1-\beta)/B \right)}{e(\lambda)-1}$-robust.
\end{lem}
\begin{proof}
Algorithm \ref{alg:LA Primal-Dual for Bahncard} makes 3 possible types of updates. For a minimal update, we have $\Delta P = \Delta D = \beta$. For a small update we have 
\begin{align*}
    \Delta P &= \left(1-\beta \right)\cdot \left(\sum_{t=t(j)-T}^{t(j)} x_t + \frac{1}{e(1/\lambda)-1}\right) + \beta \cdot \sum_{t=t(j)-T}^{t(j)} x_t + 1-\sum_{t=t(j)-T}^{t(j)} x_t \\
    &= 1+\frac{1-\beta}{e(1/\lambda)-1} = \frac{e(1/\lambda)-\beta}{e(1/\lambda)-1}
\end{align*}{}
and 
$$\Delta D = \lambda (1-\beta) + \beta = \beta (1-\lambda) + \lambda $$
hence the ratio is 
$$\frac{\Delta P}{\Delta D} = \frac{1}{\beta (1-\lambda) + \lambda} \cdot \frac{e(1/\lambda)-\beta}{e(1/\lambda)-1}$$
Similarly in the case of a big update we have 
$$\Delta P =  \frac{e(\lambda)-\beta}{e(\lambda)-1}$$ and $\Delta D  = 1$ which gives a ratio of 
$$\frac{\Delta P}{\Delta D} = \frac{e(\lambda)-\beta}{e(\lambda)-1}$$
We can conclude by Lemma \ref{lem:inequalities} (inequality \eqref{eqn:lemma12_4}) that the ratio of primal cost increase vs dual cost increase is always bounded by 
$$\frac{\Delta P}{\Delta D}\leq \frac{e(\lambda)-\beta}{e(\lambda)-1}$$ Using Lemma \ref{lem:dual_bahncard} along with weak duality is enough to conclude that the cost of the fractional solution built by the algorithm is bounded as follows
$$\textit{cost}_{\tiny{\mathcal{PDLA}}}(\mathcal A, \mathcal I,\lambda)\leq \frac{\left(e(\lambda)-\beta\right)\cdot \left(1+(1-\beta)/B \right)}{e(\lambda)-1}\cdot \OPT$$
which ends the proof.
\end{proof}

For consistency, we analyze the algorithm's cost in two parts. When the heuristic algorithm $\mathcal{A}$ buys its $i$th Bahncard at some time $t_i$, define the interval $I_i=[t_i,t_i+T]$ which represents the set of times during which this specific Bahncard is valid. This creates a family of intervals $I_1,\ldots I_k$ if $\mathcal{A}$ buys $k$ Bahncards. Note that  we can assume that all these intervals are disjoint since if the prediction $\mathcal{A}$ suggests to buy a new Bahncard before the previous one expires, it is always better to postpone this buy to the end of the validity of the current Bahncard.
\begin{lem}
\label{lem:consistency_1_Bahncard}
Denote by $\left(\Delta P\right)_{I_i}$ the increase in the primal cost of Algorithm \ref{alg:LA Primal-Dual for Bahncard} during interval $I_i$ and by cost$(\mathcal{A})_{I_i}$ what prediction $\mathcal{A}$ pays during this same interval $I_i$ (including the buy of the Bahncard at the beginning of the interval $I_i$). Then, for all $i$ we have

\begin{equation*}
    \frac{\left(\Delta P\right)_{I_i}}{\mbox{cost}(\mathcal{A})_{I_i}} \leq \frac{\left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil}{B+\beta \cdot \left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil}\cdot \frac{e(\lambda)-\beta}{e(\lambda)-1}
\end{equation*}{}
\end{lem}{}
\begin{proof}
Assume that $m$ trips are requested during this interval $I_i$. Then we first have that $cost(\mathcal{A})_{I_i}=B+\beta m$ ($\mathcal A$ buys a Bahncard then pays a discounted price for every trip in the interval $I_i$).

As for Algorithm \ref{alg:LA Primal-Dual for Bahncard}, for each trip $j$, we are possibly in the first two cases: either $\sum_{t=t(j)-T}^{t(j)}x_t\geq 1$ in which case the increase in the primal is $\Delta P = \beta$ or in the second case in which case the increase in the primal is 
\begin{equation*}
    \Delta P = (1-\beta) \cdot \left(\sum_{t=t(j)-T}^{t(j)} x_t + \frac{1}{e(\lambda)-1} \right)+\beta \cdot \sum_{t=t(j)-T}^{t(j)} x_t + 1-\sum_{t=t(j)-T}^{t(j)} x_t= 1+\frac{1-\beta}{e(\lambda)-1}
\end{equation*}

We claim that the updates of the second case can happen at most $\left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil$ times during interval $I_i$. To see this, denote by $S(l)$ the value of $\sum_{t'\geq t_i} x_{t'}$ after $l$ big updates in interval $I_i$. Note that once $\sum_{t'\geq t_i} x_{t'}\geq 1$, big updates cannot happen anymore. Hence all we need to prove is that $S\left(\left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil\right)\geq 1$.

We prove by induction that $$S(k)\geq \frac{e(k \cdot (1-\beta)/B)-1}{e(\lambda)-1}$$

This is indeed true for $k=0$ as $S(0)$ is the value of $\sum_{t'\geq t_i} x_{t'}$ before any big update was made in $I_i$ hence $S(0)\geq 0$. Now assume this is the case for some $k$ and compute 

\begin{align*}
    S(k+1) &\geq \left(1+\frac{1-\beta}{B}\right) \cdot S(k) + \frac{1-\beta}{B}\cdot \frac{1}{e(\lambda)-1}\\
    &\geq \frac{\left(1+\frac{1-\beta}{B}\right)\cdot \left(e(k \cdot (1-\beta)/B) - 1\right)+\frac{1-\beta}{B}}{e(\lambda)-1}\\
    &\geq \frac{e((k+1) \cdot (1-\beta)/B)-1}{e(\lambda)-1}
\end{align*}{}
which concludes the induction.

Hence on interval $I_i$, the total increase in the cost of the solution can be bounded as follows 
$$\left(\Delta P\right)_{I_i} \leq \min\left\lbrace \left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil, m \right\rbrace \cdot \left(1+\frac{1-\beta}{e(\lambda)-1}\right)+ \max\left\lbrace 0,\left(m- \left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil\right)\right\rbrace \cdot \beta$$

One can see that the worst case possible for the ratio $\frac{\left(\Delta P\right)_{I_i}}{\mbox{cost}(\mathcal{A})_{I_i}}$ is obtained for $m=\left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil$ and is bounded by 

$$\frac{\left(\Delta P\right)_{I_i}}{\mbox{cost}(\mathcal{A})_{I_i}} \leq 
 \frac{\left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil \cdot \left(1+\frac{1-\beta}{e(\lambda)-1}\right)}{B+\beta \cdot \left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil} = \frac{\left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil}{B+\beta \cdot \left\lceil\lambda \cdot \frac{B}{1-\beta}\right\rceil}\cdot \frac{e(\lambda)-\beta}{e(\lambda)-1}$$
\end{proof}{}

We then consider times $t$ that do not belong to any interval $I_i$. More precisely, we upper bound the value $\left(\Delta P\right)_j$ that is the increase in cost of the primal solution due to trip $j$ such that $t(j)$ does not belong to any interval $I_i$. Note that in this case the prediction always pays a cost of $1$. 

\begin{lem}
\label{lem:consistency_2_Bahncard}
For any trip $j$ such that $t(j)\notin \bigcup_i I_i $, we have that 

$$\left(\Delta P\right)_{j} \leq \frac{e(1/\lambda)-\beta}{e(1/\lambda)-1} $$
\end{lem}{}
\begin{proof}
Note that Algorithm \ref{alg:LA Primal-Dual for Bahncard} pays either the cost of a small update which is $\frac{e(1/\lambda)-\beta}{e(1/\lambda)-1}$ or the cost of a minimal update which is $\beta$.
\end{proof}{}

For simplicity and better readability, we will formulate the final theorem of this section only for $\frac{B}{1-\beta}\rightarrow \infty$.

\begin{thm*}[Theorem \ref{thm:PDLA bahncard} restated]
    For any $\lambda \in (0,1]$, any $\beta \in [0,1]$ and ${\frac{B}{1-\beta} \xrightarrow[]{} \infty }$, we have the following guarantees on any instance $\mathcal I$
  $$ \textit{cost}_{\tiny{\mathcal{PDLA}}}(\mathcal A, \mathcal I,\lambda) \leq \min \left\lbrace \frac{\lambda}{1-\beta +\lambda \beta }\cdot \frac{e^{\lambda} - \beta}{e^{\lambda} - 1}\cdot S(\mathcal A, I), \frac{e^{\lambda}-\beta}{e^{\lambda}-1}\cdot \OPT \right\rbrace$$
\end{thm*}
\begin{proof}
By taking the limit in Lemma \ref{lem:robustness Bahncard}, we see that the cost of the solution output by Algorithm \ref{alg:LA Primal-Dual for Bahncard} is at most $\frac{e^\lambda-\beta}{e^\lambda-1}\cdot \OPT$ which proves the second bound in the theorem.

For the first bound, note that we can write the final cost of the solution as 
$$\textit{cost}_{\tiny{\mathcal{PDLA}}}(\mathcal A, \mathcal I,\lambda) = \Delta P = \sum_i \left(\Delta P \right)_{I_i}+\sum_{j: t(j)\notin \bigcup_i I_i} \left(\Delta P \right)_j $$

By taking the limit in Lemma \ref{lem:consistency_1_Bahncard} we get that 
$$\sum_i \left(\Delta P \right)_{I_i}\leq \frac{\lambda}{1-\beta + \beta\lambda}\cdot \frac{e^\lambda - \beta}{e^\lambda - 1} \cdot \sum_i \textit{cost}(\mathcal{A})_{I_i}$$
and by taking the limit in Lemma \ref{lem:consistency_2_Bahncard}, we get that
$$\sum_{j: t(j)\notin \bigcup_i I_i} \left(\Delta P \right)_j \leq \frac{e^{1/\lambda}-\beta}{e^{1/\lambda}-1}\cdot \sum_{j: t(j)\notin \bigcup_i I_i} \textit{cost}(\mathcal A)_j$$

By using Lemma \ref{lem:inequalities} (inequality \eqref{eqn:lemma12_3}), we see that 
$$\max\left\lbrace \frac{\lambda}{1-\beta + \beta\lambda}\cdot \frac{e^\lambda - \beta}{e^\lambda - 1}, \frac{e^{1/\lambda}-\beta}{e^{1/\lambda}-1}\right\rbrace = \frac{\lambda}{1-\beta + \beta\lambda}\cdot \frac{e^\lambda - \beta}{e^\lambda - 1}$$
which ends the proof.

\end{proof}

We finish this section by proving that a fractional solution can be rounded online into a randomized integral solution. The expected cost of the rounded instance will be equal to the cost of the fractional solution. If the rounding is very similar to the existing rounding of \citet{ad_auctionsESA} for ski rental or TCP acknowledgement, we still include it here for completeness as the Bahncard problem was never solved in a primal-dual way. The argument is summarized in the following lemma.
\begin{lem}
Given a fractional solution $(x,d,f)$ to the Bahncard problem, it can be rounded online into an integral solution of expected cost equal to the fractional cost of $(x,d,f)$.
\end{lem}
\begin{proof}
Choose some real number $p$ uniformly at random in the interval $[0,1]$. Then arrange the variables $x_t$ on the real line (i.e. iteratively as follows, each time $t$ takes an interval $I_t$ of length $x_t$ right after the interval taken by $x_{t-1}$). Then buy a Bahncard at every time $t$ such that the interval corresponding to time $t$ contains the real number $p+k$ for some integer $k$. We check first that the expected buying cost is
\begin{equation*}
    B\cdot \sum_t \mathbbm{E}\left(\mathds{1}_{p+k\in I_t}\right) = B\cdot \sum_t x_t
\end{equation*}

Next, to compute the total expected price of the tickets, notice that if a ticket was bought in the previous $T$ time steps, we can pay a discounted price, otherwise we need to pay the full price of $1$. For a trip $j$, the probability that a ticket was bought in the previous $T$ time steps is at least $\sum_{t=t(j)-T}^{t(j)}x_t$. Hence with probability at least $\sum_{t=t(j)-T}^{t(j)}x_t\geq d_j$ we pay a price of $\beta$ and with probability $1-d_j\leq f_j$ we pay a price of $1$ which ends the proof.
\end{proof}






\section{Introduction}
\label{sec:introduction}
\input{Introduction}

\section{General PDLA method}
\label{sec:set cover main}
\input{SetCover_main}


\section{The Ski rental problem}
\label{sec:alternative ski rental}
\input{Alternative_Ski_Rental}

\section{Dynamic TCP acknowledgement}
\label{sec:tcp ack main}
\input{TCP_main}

\section{Future Directions}
\label{sec: future directions}
\input{ConclusionsAndFutureDirections}


\section*{Broader Impact}
The field of learning augmented algorithms lies in the intersection of machine learning and online algorithms, trying to combine the best of the two worlds. Learning augmented algorithms are particularly suited for critical applications where maintaining worst-case guarantees is mandatory but at the same time predictions about the future are possible. Thus, our work represents a stepping stone towards (easily) integrating ML predictions in such applications, increasing this way the possible benefits of ML to society. PDLA offers a recipe on how to incorporate predictions to tackle classical covering online problems, that is to first solve the online problem using the Primal-Dual technique and then use the prediction to change the rate at which primal and dual variables increase or decrease. We believe that since the idea behind this technique is simple and does not require too much domain-specific knowledge, it might be applicable to different problems and can also be implemented in practice.


\section*{Acknowledgments and Disclosure of Funding}
This research is supported by the Swiss National Science Foundation project 200021-184656 ``Randomness in Problem Instances and Randomized Algorithms''. Andreas Maggiori was supported by the Swiss National Science Fund (SNSF) grant n\textsuperscript{o} $200020\_182517/1$ ``Spatial Coupling of Graphical Models in Communications, Signal Processing, Computer Science and Statistical Physics''.

\nocite{*}
\bibliographystyle{plainnat}




\subsection{Plots of instances}

We briefly show in Figures \ref{fig:poisson_instance}, \ref{fig:pareto_instance}, and \ref{fig:poisson_it_instance} how typical instances under various distributions look like.

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{experiments_plot/Instance_Poisson.pdf}
    \caption{Typical instance under Poisson distribution}
    \label{fig:poisson_instance}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{experiments_plot/Instance_Pareto.pdf}
    \caption{Typical instance under Pareto distribution}
    \label{fig:pareto_instance}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.5]{experiments_plot/Instance_Poisson_iterated.pdf}
    \caption{Typical instance under iterated Poisson distribution}
    \label{fig:poisson_it_instance}
\end{figure}

\subsection{Theoretical analysis}
Recall that we define in this section \(e(z)=(1+1/d)^{z\cdot d}\) which will be roughly equal to \(e^z\) for big \(d\). The big updates are then the updates where \(z\) is set to \(\lambda\) and during a small update, \(z\) is set to \(1/\lambda\).

We first analyze the consistency of this algorithm. To this end denote by \(n_\mathcal{A}\) the number of acknowledgements sent by \(\mathcal{A}\) and by \(\textit{latency}\left(\mathcal{A} \right)\) the latency paid by the prediction \(\mathcal{A}\).
\begin{lem} 
\label{lem:consistency_TCP}
For any \(\lambda\in (0,1]\), \(d>0\),
\[\textit{c}_{\tiny{\mathcal{PDLA}}}(\mathcal A, \I,\lambda)\leq n_{\mathcal{A}}  \cdot \frac{1}{d}\cdot \frac{\left\lceil \lambda d\right\rceil}{1-e(-\lambda)} + \textit{latency}(\mathcal{A})\cdot  \frac{1}{1-e(-1/\lambda)}\]
\end{lem}
\begin{proof}
We will use a charging argument to analyze the performance of Algorithm \ref{alg:LA Primal-Dual for TCP ack}. Note that for a small update, the increase in cost of the fractional solution is 

\[\Delta P = \frac{1}{d}\left(1 - \sum_{k = t(j)}^t x_k\right)+\frac{1}{d}\cdot \left(\sum_{k = t(j)}^t x_k + \frac{1}{e(1/\lambda)-1} \right) = \frac{1}{d}\cdot \frac{1}{1-e(-1/\lambda)}\]

However, for every small update that is made, it must be that \(\mathcal{A}\) pays a latency of at least \(\frac{1}{d}\). Hence the total cost of small updates made by Algorithm \ref{alg:LA Primal-Dual for TCP ack} is at most \(\textit{latency}(\mathcal{A}) \cdot \frac{1}{1-e(-1/\lambda)}\).

Secondly we bound the total cost of big updates of our algorithm. Let \(t_0\) be a time at which \(\mathcal{A}\) sends an acknowledgment. Let \(Y\) be the set of big updates made because of jobs \(j\) that are acknowledged at time \(t_0\) by \(\mathcal{A}\) (these big updates are hence made at some time \(t\geq t_0\)). We claim that \(|Y|\leq \left\lceil \lambda d\right\rceil\).

To prove this denote by \(S(l)\) the value of \(\sum_{k=t_0}^{+\infty} x_k\) after \(l\) such big updates (there might be small updates influencing this value but only to make it bigger). Notice that once \(\sum_{k=t_0}^{+\infty} x_k\geq 1\) there is no remaining update in \(Y\). We prove by induction that 
\[ S(l)\geq \frac{(1+1/d)^l - 1}{(1+1/d)^{\lambda d}-1}\]

This is clear for \(l=0\) as \(S(0)\geq 0\). Now assume this is the case for some value \(l\) and apply a big update at time \(t\) for job \(j\) to get


\begin{align*}
    S(l+1)&=S(l)+\frac{1}{d}\cdot \left(\sum_{k=t(j)}^t x_k + \frac{1}{e(\lambda)-1}\right)\\
    &\geq S(l)\cdot (1+1/d) + \frac{1}{d(e(\lambda)-1)}\\
    &= \frac{(1+1/d)^{l+1} - 1-1/d}{(1+1/d)^{\lambda d}-1}+ \frac{1/d}{(e(\lambda)-1)}\\
    &=\frac{(1+1/d)^{l+1} - 1-1/d}{(1+1/d)^{\lambda d}-1}+ \frac{1/d}{(1+1/d)^{\lambda d}-1}\\
    &=\frac{(1+1/d)^{l+1} - 1}{(1+1/d)^{\lambda d}-1}
\end{align*}{}

Where the second inequality comes from noting that since we are considering an update due to a request $j$ acknowledged at time $t_0$ by the predicted solution, it must be that $t(j) \leq t_0$ and  $\sum_{k=t(j)}^t x_k \geq \sum_{k=t_0}^t x_k$.
Hence we get that \(S\left(\left\lceil \lambda d\right\rceil \right)\geq 1\) which implies that \(|Y|\leq \left\lceil \lambda d\right\rceil\). 

By a similar calculation as for the small update case, we have that the cost of a big update is 

\begin{equation*}
    \Delta P = \frac{1}{d}\cdot \frac{1}{1-e(-\lambda)}
\end{equation*}

Hence the total cost of these updates in \(Y\) is charged to the acknowledgement that \(\mathcal{A}\) pays at time \(t_0\) to finish the proof.
\end{proof}

Taking the limit \(d\rightarrow +\infty\) we get the following corollary:

\begin{cor}
\label{cor:TCP_consistency_asymptotic}
For any \(\lambda\in (0,1]\) and taking \(d\rightarrow +\infty\), we have that
\[\textit{c}_{\tiny{\mathcal{PDLA}}}(\mathcal A, \I,\lambda) \leq n_\mathcal{A}\cdot \frac{\lambda}{1-e^{-\lambda}}+\textit{latency}(\mathcal{A})\cdot \frac{1}{1-e^{-1/\lambda}} \]
\end{cor}{}

We then prove robustness of the algorithm with the following lemmas.

\begin{lem}
\label{lem:TCP_feasible}
Let \(y\) be the dual solution produced by Algorithm \ref{alg:LA Primal-Dual for TCP ack}. Then \(\frac{y}{1+1/d}\) is feasible.
\end{lem}{}
\begin{proof}
Notice that the constraints of the second type (i.e. \(0 \leq y_{jt} \leq 1/d\)) are always satisfied since \(0<\lambda\leq 1\). We now check that the second constraints are almost satisfied (within some factor \((1+1/d)\)). Fix a time \(t\in T\) and consider the corresponding constraint: 
\[\sum_{j | t \geq t(j)} \sum_{t' \geq t} y_{jt} \leq 1\]

Note that for a small update for some job \(j\) such that \(t(j)\leq t\) the sum above increases by \(\lambda/d\) while it increases by \(1/d\) for a big update. Notice that once we have that \(\sum_{t'\geq t} x_{t'}\geq 1\), no more such update will be performed. Denote by $S$ the value of this sum.

Notice that for a big update, the sum $S$ becomes $\left(1+\frac{1}{d} \right)\cdot S + \frac{1}{d((1+1/d)^{\lambda d} -1)}$. Similarly, for a small updates it becomes $\left(1+\frac{1}{d} \right)\cdot S + \frac{1}{d((1+1/d)^{d/\lambda} -1)}$.


Hence, if we denote by \(s\) the number of small updates in this sum and by \(b\) the number of big updates, by Lemma \ref{lem:sequence_lemma} we have that if \(\lambda s + b \geq d\) then \(\sum_{t'\geq t} x_{t'}\geq 1\). This directly implies that the value of $\sum_{j | t \geq t(j)} \sum_{t' \geq t} y_{jt}$ is at most \(1+1/d\) at the end of the algorithm (each update in the dual is of value at most \(1/d\)).

Therefore scaling down all $y_{jt}$ by a multiplicative factor of $1+1/d$ yields a feasible solution to the dual.
\end{proof}{}

\begin{lem}
\label{lem:TCP_robustness}
For \(d\rightarrow +\infty\), Algorithm \ref{alg:LA Primal-Dual for TCP ack} outputs a solution of cost at most \(\frac{1}{1-e^{-\lambda}}\cdot \OPT\)
\end{lem}{}
\begin{proof}
We first compare the increase \(\Delta P\) in the primal value to the increase \(\Delta D\) in the dual value at every update. We claim that for every update we have 
\begin{equation*}
    \frac{\Delta P}{\Delta D}\leq \frac{1}{1-e(-\lambda)}
\end{equation*}{}
In the case of a big update we directly have \(\Delta P=\frac{1}{d}\left(1+\frac{1}{e(\lambda)-1} \right)=\frac{1}{d}\cdot\frac{1}{1-e(-\lambda)}\) and \(\Delta D = \frac{1}{d}\). In the case of a small update we have \(\Delta D = \frac{\lambda}{d}\) and \(\Delta P = \frac{1}{d}\left(1+\frac{1}{e(1/\lambda)-1} \right)=\frac{1}{d}\cdot\frac{1}{1-e(-1/\lambda)}\) and we conclude applying Lemma \ref{lem:inequalities} (inequality \eqref{eqn:lemma12_1}) that we always have

\begin{equation*}
    \frac{\Delta P}{\Delta D} \leq \frac{1}{1-e(-\lambda)}
\end{equation*}

By lemma \ref{lem:TCP_feasible}, \(\frac{y}{1+1/d}\) is a feasible solution. Hence taking \(d \rightarrow +\infty\) together with the previous remark and weak duality we get the result.
\end{proof}{}

Combining Lemma \ref{cor:TCP_consistency_asymptotic} and Lemma \ref{lem:TCP_robustness} yields Theorem \ref{thm:tcp_main}.




\subsection{The PDLA algorithm and its theoretical analysis}
Our prediction consists in a collection of times \(\A\) in which the prediction suggests sending an ack. Let \(\alpha (t) \) be the next time \(t'\geq t\) when prediction sends an ack. With this definition each packet \(j\), if the prediction is followed blindly, is acknowledged at time \(\alpha (t (j))\) incurring a latency cost of \({\left(\alpha(t(j)) - t(j)\right) \cdot \frac{1}{d}}\). In the same spirit as for the ski rental problem we adapt the pure online Algorithm \ref{alg:Primal-Dual for TCP ack} into the learning augmented Algorithm \ref{alg:LA Primal-Dual for TCP ack}. Algorithm \ref{alg:LA Primal-Dual for TCP ack} adjusts the rate at which we increase the primal and dual variables according to the prediction \(\A\). Thus if a packet \(j\) at time t is "uncovered" (\(\sum_{k = t(j)}^t x_k + f_{jt} < 1\)) by our fractional solution and "covered" by \(\A\) (\(\alpha (t(j)) \leq t\)) we increase \(x_t\) at a faster rate. To simplify the description of Algorithm \ref{alg:LA Primal-Dual for TCP ack} we define \(e(z) = (1+\frac{1}{d})^{z \cdot d}\). To get to the continuous time case, we will take the limit \(d\rightarrow \infty\) so the reader should think intuitively as \(e(z)\approx e^z\). 



\begin{figure}[!h]
    \begin{minipage}[t]{0.46\textwidth}
       \vspace{0pt}
    \begin{algorithm}[H]
  \caption{\textsc{Primal Dual method for TCP acknowledgement \cite{ad_auctionsESA}.}}
  \label{alg:Primal-Dual for TCP ack}
\begin{algorithmic}
  \STATE {\bfseries Initialize:} \(x \leftarrow 0\), \(y\leftarrow 0\)
  \FORALL{times \(t\)}
  \FORALL{packages \(j\) such that \(\sum_{k = t(j)}^t x_k < 1\)}
        \STATE \(c \xleftarrow{} e(1) \), \(c' \xleftarrow{} 1/d\)
        \STATE {\scriptsize \textit{/* Primal Update}}
        \STATE \(f_{jt} \leftarrow 1 - \sum_{k = t(j)}^t x_k\)
        \STATE \(x_t \leftarrow x_t + \frac{1}{d}\cdot \left( \sum_{k = t(j)}^{t} x_k + \frac{1}{c -1}\right)\)
        \STATE {\scriptsize \textit{/* Dual Update}}
        \STATE \(y_{jt} \leftarrow c'\)
  \ENDFOR
  \ENDFOR
\end{algorithmic}
\end{algorithm}
    \end{minipage}
    \hfill
    \begin{minipage}[t]{0.01\textwidth}
    \vspace{3cm}
       {\Large \contour{black}{\(\Rightarrow\)}}
    \end{minipage}
    \hfill
    \begin{minipage}[t]{0.5\textwidth}
       \vspace{0pt}\raggedright
       \begin{algorithm}[H]
\small
  \caption{\textsc{PDLA for TCP acknowledgement}}
  \label{alg:LA Primal-Dual for TCP ack}
\begin{algorithmic}
  \STATE {\bfseries Input: \(\lambda\), \(\A\)}
  \STATE {\bfseries Initialize:} \(x \leftarrow 0\), \(y\leftarrow 0\)
  \FORALL{times \(t\)}
  \FORALL{packages \(j\) such that \(\sum_{k = t(j)}^t x_k < 1\)}
        \IF{\(t \geq \alpha(t(j))\)}
            \STATE {\scriptsize \textit{/* Prediction already acknowledged packet \(j\)}}
            \STATE \(c \xleftarrow{} e(\lambda) \), \(c' \xleftarrow{} 1/d\)
        \ELSE
            \STATE {\scriptsize \textit{/* Prediction did not acknowledge packet \(j\) yet}}
            \STATE \(c \xleftarrow{} e(1/\lambda) \), \(c' \xleftarrow{} \lambda/d\)
        \ENDIF
        \STATE {\scriptsize \textit{/* Primal Update}}
        \STATE \(f_{jt} \leftarrow 1 - \sum_{k = t(j)}^t x_k\)
        \STATE \(x_t \leftarrow x_t + \frac{1}{d}\cdot \left( \sum_{k = t(j)}^{t} x_k + \frac{1}{c -1}\right)\)
        \STATE {\scriptsize \textit{/* Dual Update}}
        \STATE \(y_{jt} \leftarrow c'\)
  \ENDFOR
  \ENDFOR
\end{algorithmic}
\end{algorithm}
    \end{minipage}
\end{figure} 	


We continue by presenting Algorithm's \ref{alg:LA Primal-Dual for TCP ack} guarantees together with a proof sketch. As before \(\I\) denotes the TCP ack problem instance which is revealed in an online fashion. The full proof is deferred to \iffullversion{appendix \ref{sec:TCP appendix}}{the supplemental material}.

\begin{thm}[PDLA for TCP-ack]
\label{thm:tcp_main}
For any prediction \(\mathcal A\), any instance \(\mathcal I\) of the TCP ack problem, any parameter \(\lambda \in (0,1]\), and \(d\rightarrow \infty\): Algorithm \ref{alg:LA Primal-Dual for TCP ack} outputs a fractional solution of cost at most
\(c_{\tiny{\mathcal{PDLA}}}(\mathcal A, \mathcal I, \lambda) \leq \min \left\lbrace \frac{\lambda}{1-e^{-\lambda }}\cdot S(\mathcal A, \mathcal I),\frac{1}{1-e^{-\lambda}}\cdot \OPT (\I) \right\rbrace \)
\end{thm}
\begin{proof}[Proof sketch]
The two bounds are proven separately. For the robustness bound, while our analysis is slightly more technical, we use the same idea as the original analysis in \cite{ad_auctionsESA}. That is, upper bounding the ratio \(\Delta P /\Delta D\) in every iteration and using weak duality. The consistency proof uses a simple charging scheme that can be seen as a generalization of our consistency proof for the ski rental problem. We essentially have two cases, big (\(c = e(\lambda)\)) and small (\(c = e(1/\lambda)\)) updates. In the case of a small update, a simple calculation reveals that the increase in cost of the solution is at most \(\Delta P=\frac{1}{d}\left(1-\sum_{k=t(j)}^{t}x_k\right)+\frac{1}{d}\left(\sum_{k=t(j)}^{t}x_k + \frac{1}{e(1/\lambda)-1}\right)=\frac{1}{d}\left(1 + \frac{1}{e(1/\lambda)-1}\right)=\frac{1}{d}\cdot \left( \frac{1}{1-e(-1/\lambda)}\right)\). Notice then whenever Algorithm \ref{alg:LA Primal-Dual for TCP ack} does a small update at time \(t\) due to request \(j\), prediction \(\A\) pays a latency cost of \(1/d\) since it has not yet acknowledged request \(j\). Hence the primal increase of cost which is at most \(\frac{1}{d}\cdot \frac{1}{1-e(-1/\lambda)}\) can be charged to the latency cost \(1/d\) paid by \(\A\) with a multiplicative factor \(\frac{1}{1-e(-1/\lambda)} \leq \frac{\lambda}{1-e(-\lambda)}\) (\iffullversion{see Lemma \ref{lem:inequalities}, inequality \eqref{eqn:lemma12_1}}{see the supplemental material}). The case of big updates is slightly different. Consider a time \(t_0\) at which \(\A\) sends an acknowledgement and consider the big updates performed by Algorithm \ref{alg:LA Primal-Dual for TCP ack} for packets \(j\) arrived before that time (\(t(j) \leq t_0\)). We claim that at most \(\left\lceil \lambda d \right\rceil \) such big updates can be made. Indeed, big updates are more aggressive (i.e. \(x_t\) increases faster), and a ``covering'' due to \(\sum_{k = t_0}^t x_k \geq 1\) is reached after only \(\left\lceil \lambda d \right\rceil\) updates (after this point, the packets arrived before time \(t_0\) will never force Algorithm \ref{alg:LA Primal-Dual for TCP ack} to make an update). Thus Algorithm's \ref{alg:LA Primal-Dual for TCP ack} cost due to these big updates is at most \(\left\lceil \lambda d \right\rceil \cdot (\textrm{cost of a big update}) = \left\lceil \lambda d \right\rceil \cdot (\frac{1}{d} \cdot \frac{\lambda}{1 - e(-\lambda)}) \) which can be charged to the cost of 1 incurred by \(\A\) for sending an ack at time \(t_0\).
\end{proof}
\subsection{Experiments}
\input{experiments}
