Basic solution to that bug with the Relay disconnect not happening. This ensures that the disconnects will happen eventually, as the host stops pinging relay on disconnect and also clients will request disconnection from hosts immediately if possible. However, a few more issues to consider addressing: We could boot the host from the lobby manually if a relay disconnect is detected. A client could leave the lobby immediately if the host has left. We need to clean up properly so that the automatic disconnect can be done repeatedly.

Assets/Scripts/Relay/RelayUtpClient.cs

         protected LocalLobby m_localLobby;
         protected NetworkDriver m_networkDriver;
         protected List<NetworkConnection> m_connections; // For clients, this has just one member, but for hosts it will have more.
+        protected bool m_IsRelayConnected { get { return m_localLobby.RelayServer != null; } }
 
         protected bool m_hasSentInitialMessage = false;
         private const float k_heartbeatPeriod = 5;
             m_localUser.onChanged -= OnLocalChange;
             Leave();
             Locator.Get.UpdateSlow.Unsubscribe(UpdateSlow);
+            m_connections.Clear();
             m_networkDriver.Dispose();
         }
         public void OnDestroy()
         private void UpdateSlow(float dt)
         {
             // Clients need to send any data over UTP periodically, or else the connection will timeout.
+            if (!m_IsRelayConnected) // However, if disconnected from Relay for some reason, we want the connection to timeout.
+                return;
             foreach (NetworkConnection connection in m_connections)
                 WriteByte(m_networkDriver, connection, "0", MsgType.Ping, 0); // The ID doesn't matter here, so send a minimal number of bytes.
         }
         protected virtual void ProcessDisconnectEvent(NetworkConnection conn, DataStreamReader strm)
         {
             // The host disconnected, and Relay does not support host migration. So, all clients should disconnect.
-            string msg = "Host disconnected! Leaving the lobby.";
+            string msg;
+            if (m_IsRelayConnected)
+                msg = "Host disconnected! Leaving the lobby.";
+            else
+                msg = "Connection to host was lost. Leaving the lobby.";
+
             Debug.LogError(msg);
             Locator.Get.Messenger.OnReceiveMessage(MessageType.DisplayErrorPopup, msg);
             Leave();
             }
         }
 
-        public void Leave()
+        public virtual void Leave()
-                connection.Disconnect(m_networkDriver);
+                WriteByte(m_networkDriver, connection, m_localUser.ID, MsgType.PlayerDisconnect, 0); // If the client breaks the connection, the host might still maintain it, so message instead.
             m_localLobby.RelayServer = null;
         }
     }

Assets/Scripts/Relay/RelayUtpHost.cs

 
         protected override void OnUpdate()
         {
+            if (!m_IsRelayConnected) // If Relay was disconnected somehow, stop taking actions that will keep the lobby alive.
+                return;
-            DoHeartbeat();
+            UpdateConnections();
         }
 
         /// <summary>
             }
             else if (msgType == MsgType.NewPlayer) // This ensures clients in builds are sent player state once they establish that they can send (and receive) events.
                 OnNewConnection(conn);
+            else if (msgType == MsgType.PlayerDisconnect) // Clients message the host when they intend to disconnect, or else the host ends up keeping the connection open.
+            {
+                conn.Disconnect(m_networkDriver);
+                UnityEngine.Debug.LogWarning("Disconnecting a client due to a disconnect message.");
+                return;
+            }
 
             // If a client has changed state, check if this changes whether all players have readied.
             if (msgType == MsgType.ReadyState)
         /// <summary>
         /// Clean out destroyed connections, and accept all new ones.
         /// </summary>
-        private void DoHeartbeat()
+        private void UpdateConnections()
         {
             for (int c = m_connections.Count - 1; c >= 0; c--)
             {
                 m_connections.Add(conn);
                 OnNewConnection(conn); // This ensures that clients in editors are sent player state once they establish a connection. The timing differs slightly from builds.
             }
+        }
+
+        public override void Leave()
+        {
+            foreach (NetworkConnection connection in m_connections)
+                connection.Disconnect(m_networkDriver);
+            m_localLobby.RelayServer = null;
         }
     }
 }

Assets/Scripts/Relay/RelayUtpSetup.cs

         protected LobbyUser m_localUser;
         protected Action<bool, RelayUtpClient> m_onJoinComplete;
 
-        public enum MsgType { Ping = 0, NewPlayer, ReadyState, PlayerName, Emote, StartCountdown, CancelCountdown, ConfirmInGame, EndInGame }
+        public enum MsgType { Ping = 0, NewPlayer, ReadyState, PlayerName, Emote, StartCountdown, CancelCountdown, ConfirmInGame, EndInGame, PlayerDisconnect }
 
         public void BeginRelayJoin(LocalLobby localLobby, LobbyUser localUser, Action<bool, RelayUtpClient> onJoinComplete)
         {