Reinforcement learning in real-life applications requires safety guarantees during exploration. Typical reinforcement learning algorithms do not provide such guarantees, and many modifications that do rely on Gaussian processes (GPs), which have a large computational cost. We propose a computationally lightweight algorithm based on the Nadaraya-Watson estimator that safely explores and optimizes constrained Markov decision processes (MDPs). Our algorithm, CoLSafe-MDP, uses an estimator that scales in constant-time with bounds on the estimates, a significant improvement from its GP-based counterparts that scale cubically with the number of data points. We then evaluate its performance in a grid-based environment and on observational Martian terrain data.
Figures & tables
Fig. 1: Performance comparison of CoLSafe-MDP against the SNO-MDP baseline in the synthetic grid environment. The leftmost panel shows the best seen reward against a normalized time step count. The dashes at the bottom indicate a transition from Phase 1 to Phase 2. The middle plot shows the size of the certified safe set against wall-clock time. The rightmost plot shows, on a logarithmic scale, the computational time taken by the two algorithms. From these figures, we see that while maintaining the same performance as the baseline, CoLSafe-MDP expands the safe set faster at a substantially lower computational cost.
Fig. 2: Safety heatmap of the Martian 40×40 -grid considered in our experiments. Unsafe regions are marked with a dashed line.
Method
∣X−∣
rˉ
Viol.
Time (s)
CoLSafe-MDP
–
0.561
0
0.79
1979
0.981
0
35.04
SNO-MDP-ES2 [ 12 ]
–
0.556
1
10.73
674
0.567
0
75.85
TABLE I: Mars terrain experiment results. For each method, the first row reports the exploration phase and the second the exploitation phase. ∣X−∣ is the number of certified safe states, rˉ the mean reward of the learnt policy, ‘Viol.’ the number of safety constraint violations, and ‘Time’ the wall-clock time in seconds.
Fig. 3: Visualizations of the path taken by the agent on the environment, overlaid with reward and safety function values. Top: safety g(s) ; bottom: reward r(s) . The paths indicate the extent of exploration during the training phase, any potential safety violations, and the final state. The agent visits more safe states with our algorithm, and both methods converge to a similar final position that maximizes reward within safe limits.
Harbin Institute of Technology, Harbin, Heilongjiang, China · The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong, China · City University of Hong Kong, Hong Kong, China