diff --git a/service/src/com/android/server/ConnectivityService.java b/service/src/com/android/server/ConnectivityService.java
index 8ec979a..7cf461e 100755
--- a/service/src/com/android/server/ConnectivityService.java
+++ b/service/src/com/android/server/ConnectivityService.java
@@ -353,6 +353,12 @@
     // connect anyway?" dialog after the user selects a network that doesn't validate.
     private static final int PROMPT_UNVALIDATED_DELAY_MS = 8 * 1000;
 
+    // How long to wait before considering that a network is bad in the absence of any form
+    // of connectivity (valid, partial, captive portal). If none has been detected after this
+    // delay, the stack considers this network bad, which may affect how it's handled in ranking
+    // according to config_networkAvoidBadWifi.
+    private static final int INITIAL_EVALUATION_TIMEOUT_MS = 20 * 1000;
+
     // Default to 30s linger time-out, and 5s for nascent network. Modifiable only for testing.
     private static final String LINGER_DELAY_PROPERTY = "persist.netmon.linger";
     private static final int DEFAULT_LINGER_DELAY_MS = 30_000;
@@ -581,12 +587,6 @@
     private static final int EVENT_SET_ACCEPT_UNVALIDATED = 28;
 
     /**
-     * used to ask the user to confirm a connection to an unvalidated network.
-     * obj  = network
-     */
-    private static final int EVENT_PROMPT_UNVALIDATED = 29;
-
-    /**
      * used internally to (re)configure always-on networks.
      */
     private static final int EVENT_CONFIGURE_ALWAYS_ON_NETWORKS = 30;
@@ -725,6 +725,14 @@
     private static final int EVENT_INGRESS_RATE_LIMIT_CHANGED = 56;
 
     /**
+     * The initial evaluation period is over for this network.
+     *
+     * If no form of connectivity has been found on this network (valid, partial, captive portal)
+     * then the stack will now consider it to have been determined bad.
+     */
+    private static final int EVENT_INITIAL_EVALUATION_TIMEOUT = 57;
+
+    /**
      * Argument for {@link #EVENT_PROVISIONING_NOTIFICATION} to indicate that the notification
      * should be shown.
      */
@@ -3791,7 +3799,17 @@
 
         private void handleNetworkTested(
                 @NonNull NetworkAgentInfo nai, int testResult, @NonNull String redirectUrl) {
-            final boolean valid = ((testResult & NETWORK_VALIDATION_RESULT_VALID) != 0);
+            final boolean valid = (testResult & NETWORK_VALIDATION_RESULT_VALID) != 0;
+            final boolean partial = (testResult & NETWORK_VALIDATION_RESULT_PARTIAL) != 0;
+            final boolean captive = !TextUtils.isEmpty(redirectUrl);
+
+            // If there is any kind of working networking, then the NAI has been evaluated
+            // once. {@see NetworkAgentInfo#setEvaluated}, which returns whether this is
+            // the first time this ever happened.
+            final boolean someConnectivity = (valid || partial || captive);
+            final boolean becameEvaluated = someConnectivity && nai.setEvaluated();
+            if (becameEvaluated) nai.updateScoreForNetworkAgentUpdate();
+
             if (!valid && shouldIgnoreValidationFailureAfterRoam(nai)) {
                 // Assume the validation failure is due to a temporary failure after roaming
                 // and ignore it. NetworkMonitor will continue to retry validation. If it
@@ -3834,8 +3852,13 @@
                 }
             } else if (partialConnectivityChanged) {
                 updateCapabilitiesForNetwork(nai);
+            } else if (becameEvaluated) {
+                // If valid or partial connectivity changed, updateCapabilities* has
+                // done the rematch.
+                rematchAllNetworksAndRequests();
             }
             updateInetCondition(nai);
+
             // Let the NetworkAgent know the state of its network
             // TODO: Evaluate to update partial connectivity to status to NetworkAgent.
             nai.onValidationStatusChanged(
@@ -3843,13 +3866,13 @@
                     redirectUrl);
 
             // If NetworkMonitor detects partial connectivity before
-            // EVENT_PROMPT_UNVALIDATED arrives, show the partial connectivity notification
+            // EVENT_INITIAL_EVALUATION_TIMEOUT arrives, show the partial connectivity notification
             // immediately. Re-notify partial connectivity silently if no internet
             // notification already there.
             if (!wasPartial && nai.partialConnectivity()) {
                 // Remove delayed message if there is a pending message.
-                mHandler.removeMessages(EVENT_PROMPT_UNVALIDATED, nai.network);
-                handlePromptUnvalidated(nai.network);
+                mHandler.removeMessages(EVENT_INITIAL_EVALUATION_TIMEOUT, nai.network);
+                handleInitialEvaluationTimeout(nai.network);
             }
 
             if (wasValidated && !nai.isValidated()) {
@@ -4949,16 +4972,11 @@
         }
     }
 
-    private void scheduleUnvalidatedPrompt(@NonNull final Network network) {
-        scheduleUnvalidatedPrompt(network, PROMPT_UNVALIDATED_DELAY_MS);
-    }
-
-    /** Schedule unvalidated prompt for testing */
+    /** Schedule evaluation timeout */
     @VisibleForTesting
-    public void scheduleUnvalidatedPrompt(@NonNull final Network network, final long delayMs) {
-        if (VDBG) log("scheduleUnvalidatedPrompt " + network);
+    public void scheduleEvaluationTimeout(@NonNull final Network network, final long delayMs) {
         mHandler.sendMessageDelayed(
-                mHandler.obtainMessage(EVENT_PROMPT_UNVALIDATED, network), delayMs);
+                mHandler.obtainMessage(EVENT_INITIAL_EVALUATION_TIMEOUT, network), delayMs);
     }
 
     @Override
@@ -5193,23 +5211,28 @@
         return false;
     }
 
-    private void handlePromptUnvalidated(Network network) {
-        if (VDBG || DDBG) log("handlePromptUnvalidated " + network);
-        NetworkAgentInfo nai = getNetworkAgentInfoForNetwork(network);
+    private void handleInitialEvaluationTimeout(@NonNull final Network network) {
+        if (VDBG || DDBG) log("handleInitialEvaluationTimeout " + network);
 
-        if (nai == null || !shouldPromptUnvalidated(nai)) {
-            return;
+        NetworkAgentInfo nai = getNetworkAgentInfoForNetwork(network);
+        if (null == nai) return;
+
+        if (nai.setEvaluated()) {
+            // If setEvaluated() returned true, the network never had any form of connectivity.
+            // This may have an impact on request matching if bad WiFi avoidance is off and the
+            // network was found not to have Internet access.
+            nai.updateScoreForNetworkAgentUpdate();
+            rematchAllNetworksAndRequests();
         }
 
+        if (!shouldPromptUnvalidated(nai)) return;
+
         // Stop automatically reconnecting to this network in the future. Automatically connecting
         // to a network that provides no or limited connectivity is not useful, because the user
         // cannot use that network except through the notification shown by this method, and the
         // notification is only shown if the network is explicitly selected by the user.
         nai.onPreventAutomaticReconnect();
 
-        // TODO: Evaluate if it's needed to wait 8 seconds for triggering notification when
-        // NetworkMonitor detects the network is partial connectivity. Need to change the design to
-        // popup the notification immediately when the network is partial connectivity.
         if (nai.partialConnectivity()) {
             showNetworkNotification(nai, NotificationType.PARTIAL_CONNECTIVITY);
         } else {
@@ -5348,8 +5371,8 @@
                     handleSetAvoidUnvalidated((Network) msg.obj);
                     break;
                 }
-                case EVENT_PROMPT_UNVALIDATED: {
-                    handlePromptUnvalidated((Network) msg.obj);
+                case EVENT_INITIAL_EVALUATION_TIMEOUT: {
+                    handleInitialEvaluationTimeout((Network) msg.obj);
                     break;
                 }
                 case EVENT_CONFIGURE_ALWAYS_ON_NETWORKS: {
@@ -9213,7 +9236,7 @@
                 networkAgent.networkMonitor().notifyNetworkConnected(params.linkProperties,
                         params.networkCapabilities);
             }
-            scheduleUnvalidatedPrompt(networkAgent.network);
+            scheduleEvaluationTimeout(networkAgent.network, INITIAL_EVALUATION_TIMEOUT_MS);
 
             // Whether a particular NetworkRequest listen should cause signal strength thresholds to
             // be communicated to a particular NetworkAgent depends only on the network's immutable,
diff --git a/service/src/com/android/server/connectivity/NetworkAgentInfo.java b/service/src/com/android/server/connectivity/NetworkAgentInfo.java
index a4c70c8..c732170 100644
--- a/service/src/com/android/server/connectivity/NetworkAgentInfo.java
+++ b/service/src/com/android/server/connectivity/NetworkAgentInfo.java
@@ -61,6 +61,7 @@
 import android.util.Pair;
 import android.util.SparseArray;
 
+import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.util.IndentingPrintWriter;
 import com.android.internal.util.WakeupMessage;
 import com.android.modules.utils.build.SdkLevel;
@@ -399,6 +400,12 @@
         return true;
     }
 
+    /** When this network ever concluded its first evaluation, or 0 if this never happened. */
+    @VisibleForTesting
+    public long getFirstEvaluationConcludedTime() {
+        return mFirstEvaluationConcludedTime;
+    }
+
     // Delay between when the network is disconnected and when the native network is destroyed.
     public int teardownDelayMs;
 
diff --git a/tests/unit/java/com/android/server/ConnectivityServiceTest.java b/tests/unit/java/com/android/server/ConnectivityServiceTest.java
index 687f157..d2a7135 100755
--- a/tests/unit/java/com/android/server/ConnectivityServiceTest.java
+++ b/tests/unit/java/com/android/server/ConnectivityServiceTest.java
@@ -3539,7 +3539,7 @@
      **/
     private int expectUnvalidationCheckWillNotify(TestNetworkAgentWrapper agent,
             NotificationType type) {
-        mService.scheduleUnvalidatedPrompt(agent.getNetwork(), 0 /* delayMs */);
+        mService.scheduleEvaluationTimeout(agent.getNetwork(), 0 /* delayMs */);
         waitForIdle();
         return expectNotification(agent, type);
     }
@@ -3561,7 +3561,7 @@
      * @return the notification ID.
      **/
     private void expectUnvalidationCheckWillNotNotify(TestNetworkAgentWrapper agent) {
-        mService.scheduleUnvalidatedPrompt(agent.getNetwork(), 0 /*delayMs */);
+        mService.scheduleEvaluationTimeout(agent.getNetwork(), 0 /*delayMs */);
         waitForIdle();
         verify(mNotificationManager, never()).notifyAsUser(anyString(), anyInt(), any(), any());
     }
@@ -3784,6 +3784,63 @@
         callback.expectCallback(CallbackEntry.LOST, mCellNetworkAgent);
     }
 
+    private void doTestFirstEvaluation(
+            @NonNull final Consumer<TestNetworkAgentWrapper> doConnect,
+            final boolean waitForSecondCaps,
+            final boolean evaluatedByValidation)
+            throws Exception {
+        final NetworkRequest request = new NetworkRequest.Builder()
+                .addTransportType(TRANSPORT_WIFI)
+                .build();
+        TestNetworkCallback callback = new TestNetworkCallback();
+        mCm.registerNetworkCallback(request, callback);
+
+        mWiFiNetworkAgent = new TestNetworkAgentWrapper(TRANSPORT_WIFI);
+        doConnect.accept(mWiFiNetworkAgent);
+        // Expect the available callbacks, but don't require specific values for their arguments
+        // since this method doesn't know how the network was connected.
+        callback.expectCallback(CallbackEntry.AVAILABLE, mWiFiNetworkAgent);
+        callback.expectCallback(CallbackEntry.NETWORK_CAPS_UPDATED, mWiFiNetworkAgent);
+        callback.expectCallback(CallbackEntry.LINK_PROPERTIES_CHANGED, mWiFiNetworkAgent);
+        callback.expectCallback(CallbackEntry.BLOCKED_STATUS, mWiFiNetworkAgent);
+        if (waitForSecondCaps) {
+            // This is necessary because of b/245893397, the same bug that happens where we use
+            // expectAvailableDoubleValidatedCallbacks.
+            callback.expectCallback(CallbackEntry.NETWORK_CAPS_UPDATED, mWiFiNetworkAgent);
+        }
+        final NetworkAgentInfo nai =
+                mService.getNetworkAgentInfoForNetwork(mWiFiNetworkAgent.getNetwork());
+        final long firstEvaluation = nai.getFirstEvaluationConcludedTime();
+        if (evaluatedByValidation) {
+            assertNotEquals(0L, firstEvaluation);
+        } else {
+            assertEquals(0L, firstEvaluation);
+        }
+        mService.scheduleEvaluationTimeout(mWiFiNetworkAgent.getNetwork(), 0L /* timeout */);
+        waitForIdle();
+        if (evaluatedByValidation) {
+            assertEquals(firstEvaluation, nai.getFirstEvaluationConcludedTime());
+        } else {
+            assertNotEquals(0L, nai.getFirstEvaluationConcludedTime());
+        }
+        mWiFiNetworkAgent.disconnect();
+        callback.expectCallback(CallbackEntry.LOST, mWiFiNetworkAgent);
+
+        mCm.unregisterNetworkCallback(callback);
+    }
+
+    @Test
+    public void testEverEvaluated() throws Exception {
+        doTestFirstEvaluation(naw -> naw.connect(true /* validated */),
+                true /* waitForSecondCaps */, true /* immediatelyEvaluated */);
+        doTestFirstEvaluation(naw -> naw.connectWithPartialConnectivity(),
+                true /* waitForSecondCaps */, true /* immediatelyEvaluated */);
+        doTestFirstEvaluation(naw -> naw.connectWithCaptivePortal(TEST_REDIRECT_URL, false),
+                true /* waitForSecondCaps */, true /* immediatelyEvaluated */);
+        doTestFirstEvaluation(naw -> naw.connect(false /* validated */),
+                false /* waitForSecondCaps */, false /* immediatelyEvaluated */);
+    }
+
     private void tryNetworkFactoryRequests(int capability) throws Exception {
         // Verify NOT_RESTRICTED is set appropriately
         final NetworkCapabilities nc = new NetworkRequest.Builder().addCapability(capability)