We consider stochastic non-stationary linear bandits where the linear parameter connecting contexts to the reward changes over time. Existing algorithms in this setting localize the policy by gradually discarding or down-weighting past data, effectively shrinking the time horizon over which learning can occur. However, in many settings historical data may still carry partial information about the reward model. We propose to leverage such data while adapting to changes, by assuming the reward model decomposes into stationary and non-stationary components. Based on this assumption, we introduce ISD-linUCB, an algorithm that uses past data to learn invariances in the reward model and subsequently exploits them to improve online performance. We show both theoretically and empirically that leveraging invariance reduces the problem dimensionality, yielding significant regret improvements in fast-changing environments when sufficient historical data is available.
Figures & tables
Figure 1: ISD-linUCB exploits historical data to improve reward predictions used by the UCB policy.
Figure 2: Regret of ISD-linUCB with oracle (Sinv,Sres) over T=100 rounds for pres∈{2,4,6,8} . For each pres the experiment is repeated 20 times. The left plot shows the average performance and the standard deviation over the 20 repetitions, the right plot shows the distribution of the regret over the 20 repetitions.
Figure 3: Cumulative regret of standard LinUCB and ISD-linUCB with oracle (Sinv,Sres) for T=100 and increasing values of context-action feature dimension p . For ISD-linUCB, the invariant component βinv is estimated using T0=2000 observations. pinv varies from 3 to 10 , while the pres is fixed to 2 . For each p the experiment is repeated 20 times.
Figure 4: Cumulative regret for T0∈{1000,3500,8000} (20 repetitions) for ISD-linUCB, in comparison with the same algorithm having oracle information and with the standard linUCB alogorithm (unaffected by T0 ). For increasing T0 , the regret of ISD-linUCB gets closer to the one of the oracle version.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Projection error for T0∈{1000,3500,8000} . The plot on the left shows the same values multiplied by T0 , confirming our assumption.
Figure 6: Cumulative regret of standard LinUCB, SW-linUCB, D-linUCB and ISD-linUCB with oracle (Sinv,Sres) for T=100 and increasing values of context-action feature dimension p . For ISD-linUCB, the invariant component βinv is estimated using T0=2000 observations. pinv varies from 3 to 10 , while the pres is fixed to 2 .
Figure 7: Cumulative regret for T0∈{1000,3500,8000} for ISD-linUCB, in comparison with the same algorithm having oracle information and with the standard linUCB alogorithm, with SW-linUCB and D-linUCB (unaffected by T0 ). For each T0 the experiment is repeated 20 times.