  The interaction between a vehicle navigation system and the driver of the
vehicle can be formulated as a model-based reinforcement learning problem,
where the navigation systems (agent) must quickly adapt to the characteristics
of the driver (environmental dynamics) to provide the best sequence of
turn-by-turn driving instructions. Most modern day navigation systems (e.g,
Google maps, Waze, Garmin) are not designed to personalize their low-level
interactions for individual users across a wide range of driving styles (e.g.,
vehicle type, reaction time, level of expertise). Towards the development of
personalized navigation systems that adapt to a variety of driving styles, we
propose an online no-regret model-based RL method that quickly conforms to the
dynamics of the current user. As the user interacts with it, the navigation
system quickly builds a user-specific model, from which navigation commands are
optimized using model predictive control. By personalizing the policy in this
way, our method is able to give well-timed driving instructions that match the
user's dynamics. Our theoretical analysis shows that our method is a no-regret
algorithm and we provide the convergence rate in the agnostic setting. Our
empirical analysis with 60+ hours of real-world user data using a driving
simulator shows that our method can reduce the number of collisions by more
than 60%.
