Online Learning with Off-Policy Feedback
This work addresses a partial observability challenge in sequential decision-making for machine learning researchers, offering incremental improvements by adapting existing pessimistic reward estimators to a new feedback model.
The paper tackles the problem of online learning in adversarial bandit settings with off-policy feedback, where rewards are observed indirectly from an unknown behavior policy, and proposes algorithms that achieve regret bounds scaling with the mismatch between comparator and behavior policies, showing improved performance for well-covered comparators in experiments.
We study the problem of online learning in adversarial bandit problems under a partial observability model called off-policy feedback. In this sequential decision making problem, the learner cannot directly observe its rewards, but instead sees the ones obtained by another unknown policy run in parallel (behavior policy). Instead of a standard exploration-exploitation dilemma, the learner has to face another challenge in this setting: due to limited observations outside of their control, the learner may not be able to estimate the value of each policy equally well. To address this issue, we propose a set of algorithms that guarantee regret bounds that scale with a natural notion of mismatch between any comparator policy and the behavior policy, achieving improved performance against comparators that are well-covered by the observations. We also provide an extension to the setting of adversarial linear contextual bandits, and verify the theoretical guarantees via a set of experiments. Our key algorithmic idea is adapting the notion of pessimistic reward estimators that has been recently popular in the context of off-policy reinforcement learning.