diff --git a/update_manager/chromeos_policy.cc b/update_manager/chromeos_policy.cc
index 8a2e2c2..86f53ce 100644
--- a/update_manager/chromeos_policy.cc
+++ b/update_manager/chromeos_policy.cc
@@ -406,28 +406,35 @@
 
   PRNG prng(*seed);
 
+  // If this is the first attempt, compute and return an initial value.
   if (!last_checked_time || *last_checked_time < *updater_started_time) {
-    // First attempt.
     *next_update_check = *updater_started_time + FuzzedInterval(
         &prng, kTimeoutInitialInterval, kTimeoutRegularFuzz);
     return EvalStatus::kSucceeded;
   }
-  // Check for previous failed attempts to implement the exponential backoff.
+
+  // Check for previous failed attempts to implement an exponential backoff.
   const unsigned int* consecutive_failed_update_checks = ec->GetValue(
       state->updater_provider()->var_consecutive_failed_update_checks());
   POLICY_CHECK_VALUE_AND_FAIL(consecutive_failed_update_checks, error);
 
-  int interval = kTimeoutInitialInterval;
+  int interval = kTimeoutPeriodicInterval;
+  int fuzz = kTimeoutRegularFuzz;
   for (unsigned int i = 0; i < *consecutive_failed_update_checks; ++i) {
     interval *= 2;
+    fuzz = 0;  // In case of backoff, fuzz is different (see below).
     if (interval > kTimeoutMaxBackoffInterval) {
       interval = kTimeoutMaxBackoffInterval;
       break;
     }
   }
 
+  // Defer to a fuzz of +/-(interval / 2) in case of backoff.
+  if (fuzz == 0)
+    fuzz = interval;
+
   *next_update_check = *last_checked_time + FuzzedInterval(
-      &prng, interval, kTimeoutRegularFuzz);
+      &prng, interval, fuzz);
   return EvalStatus::kSucceeded;
 }
 
diff --git a/update_manager/chromeos_policy.h b/update_manager/chromeos_policy.h
index d296689..b7bbdfc 100644
--- a/update_manager/chromeos_policy.h
+++ b/update_manager/chromeos_policy.h
@@ -63,6 +63,8 @@
   friend class UmChromeOSPolicyTest;
   FRIEND_TEST(UmChromeOSPolicyTest,
               FirstCheckIsAtMostInitialIntervalAfterStart);
+  FRIEND_TEST(UmChromeOSPolicyTest, RecurringCheckBaseIntervalAndFuzz);
+  FRIEND_TEST(UmChromeOSPolicyTest, RecurringCheckBackoffIntervalAndFuzz);
   FRIEND_TEST(UmChromeOSPolicyTest, ExponentialBackoffIsCapped);
   FRIEND_TEST(UmChromeOSPolicyTest, UpdateCheckAllowedWaitsForTheTimeout);
   FRIEND_TEST(UmChromeOSPolicyTest,
diff --git a/update_manager/chromeos_policy_unittest.cc b/update_manager/chromeos_policy_unittest.cc
index 2eba5d2..23c0c2b 100644
--- a/update_manager/chromeos_policy_unittest.cc
+++ b/update_manager/chromeos_policy_unittest.cc
@@ -147,13 +147,62 @@
 TEST_F(UmChromeOSPolicyTest, FirstCheckIsAtMostInitialIntervalAfterStart) {
   Time next_update_check;
 
+  // Set the last update time so it'll appear as if this is a first update check
+  // in the lifetime of the current updater.
+  fake_state_.updater_provider()->var_last_checked_time()->reset(
+      new Time(fake_clock_.GetWallclockTime() - TimeDelta::FromMinutes(10)));
+
   ExpectPolicyStatus(EvalStatus::kSucceeded,
                      &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
 
   EXPECT_LE(fake_clock_.GetWallclockTime(), next_update_check);
-  EXPECT_GE(fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
-      ChromeOSPolicy::kTimeoutInitialInterval +
-      ChromeOSPolicy::kTimeoutRegularFuzz), next_update_check);
+  EXPECT_GE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          ChromeOSPolicy::kTimeoutInitialInterval +
+          ChromeOSPolicy::kTimeoutRegularFuzz / 2),
+      next_update_check);
+}
+
+TEST_F(UmChromeOSPolicyTest, RecurringCheckBaseIntervalAndFuzz) {
+  // Ensure that we're using the correct interval (kPeriodicInterval) and fuzz
+  // (kTimeoutRegularFuzz) as base values for period updates.
+  Time next_update_check;
+
+  ExpectPolicyStatus(EvalStatus::kSucceeded,
+                     &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
+
+  EXPECT_LE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          ChromeOSPolicy::kTimeoutPeriodicInterval -
+          ChromeOSPolicy::kTimeoutRegularFuzz / 2),
+      next_update_check);
+  EXPECT_GE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          ChromeOSPolicy::kTimeoutPeriodicInterval +
+          ChromeOSPolicy::kTimeoutRegularFuzz / 2),
+      next_update_check);
+}
+
+TEST_F(UmChromeOSPolicyTest, RecurringCheckBackoffIntervalAndFuzz) {
+  // Ensure that we're properly backing off and fuzzing in the presence of
+  // failed updates attempts.
+  Time next_update_check;
+
+  fake_state_.updater_provider()->var_consecutive_failed_update_checks()->
+      reset(new unsigned int(2));  // NOLINT(readability/casting)
+
+  ExpectPolicyStatus(EvalStatus::kSucceeded,
+                     &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
+
+  int expected_interval = ChromeOSPolicy::kTimeoutPeriodicInterval * 4;
+  EXPECT_LE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          expected_interval - expected_interval / 2),
+      next_update_check);
+  EXPECT_GE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          expected_interval + expected_interval / 2),
+      next_update_check);
 }
 
 TEST_F(UmChromeOSPolicyTest, ExponentialBackoffIsCapped) {
@@ -161,15 +210,20 @@
 
   fake_state_.updater_provider()->var_consecutive_failed_update_checks()->
       reset(new unsigned int(100));  // NOLINT(readability/casting)
+
   ExpectPolicyStatus(EvalStatus::kSucceeded,
                      &ChromeOSPolicy::NextUpdateCheckTime, &next_update_check);
 
-  EXPECT_LE(fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
-      ChromeOSPolicy::kTimeoutMaxBackoffInterval -
-      ChromeOSPolicy::kTimeoutRegularFuzz - 1), next_update_check);
-  EXPECT_GE(fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
-      ChromeOSPolicy::kTimeoutMaxBackoffInterval +
-      ChromeOSPolicy::kTimeoutRegularFuzz), next_update_check);
+  EXPECT_LE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          ChromeOSPolicy::kTimeoutMaxBackoffInterval -
+          ChromeOSPolicy::kTimeoutMaxBackoffInterval / 2),
+      next_update_check);
+  EXPECT_GE(
+      fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(
+          ChromeOSPolicy::kTimeoutMaxBackoffInterval +
+          ChromeOSPolicy::kTimeoutMaxBackoffInterval /2),
+      next_update_check);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCheckAllowedWaitsForTheTimeout) {