MCMC with substitutions and multi-armed bandits with covariates : theory and applications