diff --git a/service/src/com/android/server/connectivity/FullScore.java b/service/src/com/android/server/connectivity/FullScore.java
index 22a820b..aec4a71 100644
--- a/service/src/com/android/server/connectivity/FullScore.java
+++ b/service/src/com/android/server/connectivity/FullScore.java
@@ -85,13 +85,23 @@
     /** @hide */
     public static final int POLICY_IS_INVINCIBLE = 56;
 
+    // This network has undergone initial validation.
+    //
+    // The stack considers that any result finding some working connectivity (valid, partial,
+    // captive portal) is an initial validation. Negative result (not valid), however, is not
+    // considered initial validation until {@link ConnectivityService#PROMPT_UNVALIDATED_DELAY_MS}
+    // have elapsed. This is because some networks may spuriously fail for a short time immediately
+    // after associating. If no positive result is found after the timeout has elapsed, then
+    // the network has been evaluated once.
+    public static final int POLICY_EVER_EVALUATED = 55;
+
     // The network agent has communicated that this network no longer functions, and the underlying
     // native network has been destroyed. The network will still be reported to clients as connected
     // until a timeout expires, the agent disconnects, or the network no longer satisfies requests.
     // This network should lose to an identical network that has not been destroyed, but should
     // otherwise be scored exactly the same.
     /** @hide */
-    public static final int POLICY_IS_DESTROYED = 55;
+    public static final int POLICY_IS_DESTROYED = 54;
 
     // To help iterate when printing
     @VisibleForTesting
@@ -144,6 +154,7 @@
      * @param everValidated whether this network has ever validated
      * @param avoidUnvalidated whether the user said in UI to avoid this network when unvalidated
      * @param yieldToBadWiFi whether this network yields to a previously validated wifi gone bad
+     * @param everEvaluated whether this network ever evaluated at least once
      * @param destroyed whether this network has been destroyed pending a replacement connecting
      * @return a FullScore that is appropriate to use for ranking.
      */
@@ -153,7 +164,7 @@
     public static FullScore fromNetworkScore(@NonNull final NetworkScore score,
             @NonNull final NetworkCapabilities caps, @NonNull final NetworkAgentConfig config,
             final boolean everValidated, final boolean avoidUnvalidated,
-            final boolean yieldToBadWiFi, final boolean destroyed) {
+            final boolean yieldToBadWiFi, final boolean everEvaluated, final boolean destroyed) {
         return withPolicies(score.getPolicies(),
                 score.getKeepConnectedReason(),
                 caps.hasCapability(NET_CAPABILITY_VALIDATED),
@@ -164,6 +175,7 @@
                 caps.hasCapability(NET_CAPABILITY_NOT_METERED),
                 yieldToBadWiFi,
                 false /* invincible */, // only prospective scores can be invincible
+                everEvaluated,
                 destroyed);
     }
 
@@ -198,15 +210,17 @@
         // Prospective scores are always unmetered, because unmetered networks are stronger
         // than metered networks, and it's not known in advance whether the network is metered.
         final boolean unmetered = true;
-        // A network can only be destroyed once it has connected.
-        final boolean destroyed = false;
         // A prospective score is invincible if the legacy int in the filter is over the maximum
         // score.
         final boolean invincible = score.getLegacyInt() > NetworkRanker.LEGACY_INT_MAX;
+        // A prospective network will eventually be evaluated.
+        final boolean everEvaluated = true;
+        // A network can only be destroyed once it has connected.
+        final boolean destroyed = false;
         return withPolicies(score.getPolicies(), KEEP_CONNECTED_NONE,
-                mayValidate, everValidated, vpn, everUserSelected, acceptUnvalidated,
-                avoidUnvalidated, unmetered,
-                yieldToBadWiFi, invincible, destroyed);
+                mayValidate, everValidated, vpn, everUserSelected,
+                acceptUnvalidated, avoidUnvalidated, unmetered, yieldToBadWiFi,
+                invincible, everEvaluated, destroyed);
     }
 
     /**
@@ -224,6 +238,7 @@
             final boolean everValidated,
             final boolean avoidUnvalidated,
             final boolean yieldToBadWifi,
+            final boolean everEvaluated,
             final boolean destroyed) {
         return withPolicies(mPolicies, mKeepConnectedReason,
                 caps.hasCapability(NET_CAPABILITY_VALIDATED),
@@ -234,6 +249,7 @@
                 caps.hasCapability(NET_CAPABILITY_NOT_METERED),
                 yieldToBadWifi,
                 false /* invincible */, // only prospective scores can be invincible
+                everEvaluated,
                 destroyed);
     }
 
@@ -251,6 +267,7 @@
             final boolean isUnmetered,
             final boolean yieldToBadWiFi,
             final boolean invincible,
+            final boolean everEvaluated,
             final boolean destroyed) {
         return new FullScore((externalPolicies & EXTERNAL_POLICIES_MASK)
                 | (isValidated       ? 1L << POLICY_IS_VALIDATED : 0)
@@ -262,6 +279,7 @@
                 | (isUnmetered       ? 1L << POLICY_IS_UNMETERED : 0)
                 | (yieldToBadWiFi    ? 1L << POLICY_YIELD_TO_BAD_WIFI : 0)
                 | (invincible        ? 1L << POLICY_IS_INVINCIBLE : 0)
+                | (everEvaluated     ? 1L << POLICY_EVER_EVALUATED : 0)
                 | (destroyed         ? 1L << POLICY_IS_DESTROYED : 0),
                 keepConnectedReason);
     }
diff --git a/service/src/com/android/server/connectivity/NetworkAgentInfo.java b/service/src/com/android/server/connectivity/NetworkAgentInfo.java
index d7be421..a4c70c8 100644
--- a/service/src/com/android/server/connectivity/NetworkAgentInfo.java
+++ b/service/src/com/android/server/connectivity/NetworkAgentInfo.java
@@ -377,6 +377,28 @@
         return 0L != mPartialConnectivityTime;
     }
 
+    // Timestamp (SystemClock.elapsedRealTime()) at which the first validation attempt concluded,
+    // or timed out after {@link ConnectivityService#PROMPT_UNVALIDATED_DELAY_MS}. 0 if not yet.
+    private long mFirstEvaluationConcludedTime;
+
+    /**
+     * Notify this NAI that this network has been evaluated.
+     *
+     * The stack considers that any result finding some working connectivity (valid, partial,
+     * captive portal) is an initial validation. Negative result (not valid), however, is not
+     * considered initial validation until {@link ConnectivityService#PROMPT_UNVALIDATED_DELAY_MS}
+     * have elapsed. This is because some networks may spuriously fail for a short time immediately
+     * after associating. If no positive result is found after the timeout has elapsed, then
+     * the network has been evaluated once.
+     *
+     * @return true the first time this is called on this object, then always returns false.
+     */
+    public boolean setEvaluated() {
+        if (0L != mFirstEvaluationConcludedTime) return false;
+        mFirstEvaluationConcludedTime = SystemClock.elapsedRealtime();
+        return true;
+    }
+
     // Delay between when the network is disconnected and when the native network is destroyed.
     public int teardownDelayMs;
 
@@ -975,7 +997,8 @@
         final NetworkCapabilities oldNc = networkCapabilities;
         networkCapabilities = nc;
         mScore = mScore.mixInScore(networkCapabilities, networkAgentConfig, everValidated(),
-                0L != getAvoidUnvalidated(), yieldToBadWiFi(), isDestroyed());
+                0L != getAvoidUnvalidated(), yieldToBadWiFi(),
+                0L != mFirstEvaluationConcludedTime, isDestroyed());
         final NetworkMonitorManager nm = mNetworkMonitor;
         if (nm != null) {
             nm.notifyNetworkCapabilitiesChanged(nc);
@@ -1178,7 +1201,8 @@
      */
     public void setScore(final NetworkScore score) {
         mScore = FullScore.fromNetworkScore(score, networkCapabilities, networkAgentConfig,
-                everValidated(), 0L == getAvoidUnvalidated(), yieldToBadWiFi(), isDestroyed());
+                everValidated(), 0L == getAvoidUnvalidated(), yieldToBadWiFi(),
+                0L != mFirstEvaluationConcludedTime, isDestroyed());
     }
 
     /**
@@ -1188,7 +1212,8 @@
      */
     public void updateScoreForNetworkAgentUpdate() {
         mScore = mScore.mixInScore(networkCapabilities, networkAgentConfig,
-                everValidated(), 0L != getAvoidUnvalidated(), yieldToBadWiFi(), isDestroyed());
+                everValidated(), 0L != getAvoidUnvalidated(), yieldToBadWiFi(),
+                0L != mFirstEvaluationConcludedTime, isDestroyed());
     }
 
     /**
diff --git a/tests/unit/java/com/android/server/connectivity/FullScoreTest.kt b/tests/unit/java/com/android/server/connectivity/FullScoreTest.kt
index c8a62be..b39e960 100644
--- a/tests/unit/java/com/android/server/connectivity/FullScoreTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/FullScoreTest.kt
@@ -29,6 +29,7 @@
 import com.android.server.connectivity.FullScore.MAX_CS_MANAGED_POLICY
 import com.android.server.connectivity.FullScore.MIN_CS_MANAGED_POLICY
 import com.android.server.connectivity.FullScore.POLICY_ACCEPT_UNVALIDATED
+import com.android.server.connectivity.FullScore.POLICY_EVER_EVALUATED
 import com.android.server.connectivity.FullScore.POLICY_EVER_USER_SELECTED
 import com.android.server.connectivity.FullScore.POLICY_IS_DESTROYED
 import com.android.server.connectivity.FullScore.POLICY_IS_UNMETERED
@@ -56,6 +57,7 @@
         vpn: Boolean = false,
         onceChosen: Boolean = false,
         acceptUnvalidated: Boolean = false,
+        everEvaluated: Boolean = true,
         destroyed: Boolean = false
     ): FullScore {
         val nac = NetworkAgentConfig.Builder().apply {
@@ -67,7 +69,7 @@
             if (validated) addCapability(NetworkCapabilities.NET_CAPABILITY_VALIDATED)
         }.build()
         return mixInScore(nc, nac, validated, false /* avoidUnvalidated */,
-                false /* yieldToBadWifi */, destroyed)
+                false /* yieldToBadWifi */, everEvaluated, destroyed)
     }
 
     private val TAG = this::class.simpleName
@@ -123,6 +125,7 @@
         assertTrue(ns.withPolicies(onceChosen = true).hasPolicy(POLICY_EVER_USER_SELECTED))
         assertTrue(ns.withPolicies(acceptUnvalidated = true).hasPolicy(POLICY_ACCEPT_UNVALIDATED))
         assertTrue(ns.withPolicies(destroyed = true).hasPolicy(POLICY_IS_DESTROYED))
+        assertTrue(ns.withPolicies(everEvaluated = true).hasPolicy(POLICY_EVER_EVALUATED))
     }
 
     @Test