  We study the challenging exploration incentive problem in both bandit and
reinforcement learning, where the rewards are scale-free and potentially
unbounded, driven by real-world scenarios and differing from existing work.
Past works in reinforcement learning either assume costly interactions with an
environment or propose algorithms finding potentially low quality local maxima.
Motivated by EXP-type methods that integrate multiple agents (experts) for
exploration in bandits with the assumption that rewards are bounded, we propose
new algorithms, namely EXP4.P and EXP4-RL for exploration in the unbounded
reward case, and demonstrate their effectiveness in these new settings.
Unbounded rewards introduce challenges as the regret cannot be limited by the
number of trials, and selecting suboptimal arms may lead to infinite regret.
Specifically, we establish EXP4.P's regret upper bounds in both bounded and
unbounded linear and stochastic contextual bandits. Surprisingly, we also find
that by including one sufficiently competent expert, EXP4.P can achieve global
optimality in the linear case. This unbounded reward result is also applicable
to a revised version of EXP3.P in the Multi-armed Bandit scenario. In EXP4-RL,
we extend EXP4.P from bandit scenarios to reinforcement learning to incentivize
exploration by multiple agents, including one high-performing agent, for both
efficiency and excellence. This algorithm has been tested on
difficult-to-explore games and shows significant improvements in exploration
compared to state-of-the-art.
