Bound-Based Policy

Our second policy does not attempt to fit a divergence curve based on a generative model. Instead, it places conservative bounds on divergence, and uses the bounds to adjust the refresh period $\phi_P$ adaptively.

In addition to the $h$ change profiles, for each page the bound-based policy maintains a reference time $t_R$. The policy attempts to find the optimal time for the next refresh, $t_R + \hat{\phi}_P$, where $\hat{\phi}_P$ denotes the optimal refresh period. Once the policy believes it has reached or passed time $t_R + \hat{\phi}_P$ it resets the reference time $t_R$ to the current time, and repeats the process. Each iteration is seeded with the refresh period used in the prior iteration, so that the process converges (assuming the page behavior is stationary).

The exact policy is as follows:

1. Determine divergence bounds. For each change profile, determine upper and lower bounds on divergence as shown in Figure 7. The upper bound curve represents the extreme situation where the jump in divergence between two successive observations occurs immediately following the first observation. The lower bound curve represents the opposite extreme, in which the jump in divergence occurs immediately prior to the second observation. This manner of fitting divergence bounds is conservative: it assumes no model other than monotonic divergence.
   
2. Combine divergence bounds. Combine the upper bounds from the $h$ change profiles into a single one by averaging. Combine the lower bounds in the same fashion.
   
3. Determine utility bounds. Compute the area under the divergence upper bound curve, in the interval $[0, t - t_R]$, where $t$ is the current time and $t_R$ is the reference time. Do the same for the divergence lower bound curve. Label these two areas $A_{\mathit{max}}$ and $A_{\mathit{min}}$, respectively, as shown in Figure 7. Then compute corresponding bounds on utility $U$ as per Equation 4, yielding $U_{\mathit{min}}$ and $U_{\mathit{max}}$ respectively.
   
4. Adjust refresh period and reference time.
   • If $U_{\mathit{max}} < T$, set $\phi_P := (t - t_R) \cdot 2$.
   • If $U_{\mathit{min}} \ge T$, reset the reference time to the present time ($t_R := t$), and set $\phi_P := \phi_P / 2$.

Figure 7: A change profile, with lower and upper bounds on the area under the divergence curve.

The rationale behind the above policy is that if the upper bound on utility is below the utility threshold $T$, the period $(t - t_R)$ was shorter than the optimal refresh period $\hat{\phi}_P$, so we should continue to explore larger refresh periods. We do so by doubling the quantity $(t - t_R)$ and scheduling the next refresh that many time units in the future. On the other hand, if the lower bound on utility is above the utility threshold, the period $(t - t_R)$ was longer than the optimal period $\hat{\phi}_P$, so we need to start over with a new reference time and explore shorter refresh periods. To ensure that we use a small enough period to start with, we use half of the current period $\phi_P$.

There is a third case in which the utility bounds straddle the utility threshold, i.e., $U_{\mathit{min}} < T \le U_{\mathit{max}}$. In this case we take the neutral action of leaving the refresh period as it is.