Curve-Fitting vs. Bound-Based Policy

Figure 9: Steady-state performance of online policies, on high-quality data set.

figure

In our first experiment, we compare the performance of our two online revisitation policies: the one based on curve-fitting (Section 4.2) and the one based on divergence bounds (Section 4.3).

We perform separate measurements of warm-up behavior and steady-state behavior. Warm-up behavior occurs during the time following discovery of a new page, while an online policy focuses on learning the page's change patterns. Steady-state behavior follows, wherein the policy focuses primarily on exploiting its accumulated understanding of the page.

Figure 8 shows the policies' warm-up behavior--their performance in the first 30 days of our high-quality data set. Figure 9 shows their steady-state behavior--their performance in the final 30 days (there are 60 days total). In both graphs refresh cost is plotted on the x-axis, and average fragment staleness is plotted on the y-axis.

The different points associated with a policy correspond to different utility threshold ($T$) values. For the bound-based policy we used $h = 5$ change profiles, and risk parameter $\rho = 10$. For the curve-fitting policy we again used $h = 5$, and we tuned the learning factor $l$ such that the investment in learning is proportional to the refresh cost incurred.

For reference, in both graphs we also show the performance of uniform refreshing and of the offline FS-D policy (Section 3.4). Ideally no policy should perform worse than uniform refreshing. FS-D is a hypothetical policy that has full knowledge of the page's behavior even when it is not being refreshed. It is effectively impossible for an online policy to approach the performance of an offline one.

From Figure 8 we see that during warm-up the curve-fitting and bound-based policies perform about the same amount of exploration (reflected as refresh cost). For a given exploration cost, the staleness level during warm-up roughly coincides with uniform refreshing. Turning to Figure 9 we see that in steady-state both of our policies perform significantly better than uniform refreshing, with curve-fitting slightly ahead of bound-based.