  We study reinforcement learning in the presence of an unknown reward
perturbation. Existing methodologies for this problem make strong assumptions
including reward smoothness, known perturbations, and/or perturbations that do
not modify the optimal policy. We study the case of unknown arbitrary
perturbations that discretize and shuffle reward space, but have the property
that the true reward belongs to the most frequently observed class after
perturbation. This class of perturbations generalizes existing classes (and, in
the limit, all continuous bounded perturbations) and defeats existing methods.
We introduce an adaptive distributional reward critic and show theoretically
that it can recover the true rewards under technical conditions. Under the
targeted perturbation in discrete and continuous control tasks, we win/tie the
highest return in 40/57 settings (compared to 16/57 for the best baseline).
Even under the untargeted perturbation, we still win an edge over the baseline
designed especially for that setting.
