  We propose a bandit algorithm that explores purely by randomizing its past
observations. In particular, the sufficient optimism in the mean reward
estimates is achieved by exploiting the variance in the past observed rewards.
We name the algorithm Capitalizing On Rewards (CORe). The algorithm is general
and can be easily applied to different bandit settings. The main benefit of
CORe is that its exploration is fully data-dependent. It does not rely on any
external noise and adapts to different problems without parameter tuning. We
derive a $\tilde O(d\sqrt{n\log K})$ gap-free bound on the $n$-round regret of
CORe in a stochastic linear bandit, where $d$ is the number of features and $K$
is the number of arms. Extensive empirical evaluation on multiple synthetic and
real-world problems demonstrates the effectiveness of CORe.
