Probabilistic Exploration in Planning while Learning
  Sequential decision tasks with incomplete information are characterized by
the exploration problem; namely the trade-off between further exploration for
learning more about the environment and immediate exploitation of the accrued
information for decision-making. Within artificial intelligence, there has been
an increasing interest in studying planning-while-learning algorithms for these
decision tasks. In this paper we focus on the exploration problem in
reinforcement learning and Q-learning in particular. The existing exploration
strategies for Q-learning are of a heuristic nature and they exhibit limited
scaleability in tasks with large (or infinite) state and action spaces.
Efficient experimentation is needed for resolving uncertainties when possible
plans are compared (i.e. exploration). The experimentation should be sufficient
for selecting with statistical significance a locally optimal plan (i.e.
exploitation). For this purpose, we develop a probabilistic hill-climbing
algorithm that uses a statistical selection procedure to decide how much
exploration is needed for selecting a plan which is, with arbitrarily high
probability, arbitrarily close to a locally optimal one. Due to its generality
the algorithm can be employed for the exploration strategy of robust
Q-learning. An experiment on a relatively complex control task shows that the
proposed exploration strategy performs better than a typical exploration
strategy.
