diff --git a/python/ray/autoscaler/autoscaler.py b/python/ray/autoscaler/autoscaler.py
index <HASH>..<HASH> 100644
--- a/python/ray/autoscaler/autoscaler.py
+++ b/python/ray/autoscaler/autoscaler.py
@@ -491,8 +491,10 @@ class StandardAutoscaler(object):
     def recover_if_needed(self, node_id):
         if not self.can_update(node_id):
             return
-        last_heartbeat_time = self.load_metrics.last_heartbeat_time_by_ip.get(
-            self.provider.internal_ip(node_id), 0)
+        key = self.provider.internal_ip(node_id)
+        if key not in self.load_metrics.last_heartbeat_time_by_ip:
+            self.load_metrics.last_heartbeat_time_by_ip[key] = time.time()
+        last_heartbeat_time = self.load_metrics.last_heartbeat_time_by_ip[key]
         delta = time.time() - last_heartbeat_time
         if delta < AUTOSCALER_HEARTBEAT_TIMEOUT_S:
             return
[autoscaler] Allow more than 5s from node creation to first heartbeat (#<I>)