Revisiting Dynamic Programming for Exploration: Insights from a Simple Dual Control Problem

The dual control problem, first introduced by Feldbaum in the 1960s, is recognized as encapsulating the "exploration versus exploitation" dilemma, central to online learning and control. Numerous heuristic-based exploration methods have been developed to facilitate active learning. However, the theoretically optimal solution provided by dynamic programming (DP) remains computationally intractable for most problems due to the curse of dimensionality. In this paper, we revisit the DP framework within the context of regret minimization for a simple real-time optimization problem, aiming to identify valuable insights and uncover new avenues for simplified DP-based exploration strategies. By deriving the two-horizon DP solution in our simple setting, we observe that the optimal input is obtained by solving a closed-form optimization problem composed of two distinct components representing exploration and exploitation separately, clearly highlighting their inherent trade-off. For longer horizons, receding and cyclic horizon control based on the iterative application of the two-horizon DP provide possible approximations, reducing computational complexity while yielding useful suboptimal control policies. A key advantage of the DP-based exploration method is its ability to automatically adjust the exploration based on the current exploitation and system uncertainty. The proposed method is studied numerically through comparative evaluations against classical heuristic exploration methods from the literature.