Per Curiam Opinion; Partial Concurrence and Partial Dissent by Judge FERNANDEZ; Partial Concurrence and Partial Dissent by Judge THOMAS.

I. INTRODUCTION

Robert A. Hood, Warden of the Federal Correctional Institution, Sheridan, Oregon, appeals the district court’s grant of habeas corpus relief, 28 U.S.C. § 2241 , to a number of prisoners. 2 Each of them had been subjected to the Bureau of Prisons’ determination that certain categories of prisoners would not be granted early release pursuant to the provisions of 18 U.S.C. § 3621 (e)(2)(B). One group, which we will call the Gavis Group, 3 had not even been provisionally admitted to a substance abuse treatment program at the time that the Bureau adopted its exclusionary categories. When the Bureau adopted its exclusionary categories, the other group, which we will call the Bowen Group, 4 had received provisional eligibility for early release after completing a substance abuse treatment program, but had not yet entered a program.

*1217 The Bowen Group has cross appealed because, after issuing its judgment, the district court issued a clarifying order, which, as the group’s members see it, reduced their relief below that first intended.

We reverse the district court as to the Gavis Group, but affirm as to the Bowen Group.

II. BACKGROUND

This case revolves around a program created by Congress for the purpose of providing substance abuse treatment to prisoners. It directed the Bureau to “make available appropriate substance abuse treatment for each prisoner the Bureau determines has a treatable condition of substance addiction or abuse.” 18 U.S.C. § 3621 (b). In order to give at least some prisoners an added incentive to participate in a substance abuse treatment program, Congress also provided that “[t]he period a prisoner convicted of a nonviolent offense remains in custody after successfully completing a treatment program may be reduced by the Bureau of Prisons, but such reduction may not be more than one year from the term the prisoner must otherwise serve.” 18 U.S.C. § 3621 (e)(2)(B).

For some time, the Bureau has been of the belief that a prisoner whose crime of conviction involved the possession, carrying, or use of a firearm should be ineligible for early release. At first, the Bureau implemented that belief by decreeing that those possessors of firearms had committed crimes of violence, and, therefore, had not been “convicted of a nonviolent offense.” Id. We declared that the Bureau thereby misinterpreted the meaning of “nonviolent offense” because it could not declare that possession of a firearm, either as the very offense of conviction or as an enhancement, was itself enough to make a crime one of violence. See Davis v. Crabtree, 109 F.3d 566, 569 (9th Cir.1997); Donmey v. Crabtree, 100 F.3d 662, 670 (9th Cir.1996).

The Bureau acceded to that interpretation, but, nothing deterred from its continuing belief that individuals in that category should not be given early release into the community, it determined that it would not rest its categorical exclusion of them on a direct interpretation of the specific statutory language, “nonviolent offense.” Rather, it would exercise its discretion under the statute to refuse them early release, regardless of that language. Therefore, it issued a change notice to the Early Release Qualifications Chapter of its Drug Abuse Manual, in which it declared, as pertinent here:

CN — 03, P.S. 5330.10 (October 9,1997).

On October 15, 1997, the Bureau also published an interim regulation, in which it explained, in pertinent part, that:

Drug Abuse Treatment and Intensive Confinement Center Programs: Early Release Consideration, 62 Fed.Reg. 53690 (1997) (interim rule). True to its explanation, the rule provided that “as an exercise of discretion ... inmates whose current offense is a felony ... that involved the carrying, possession, or use of a firearm” were categorically excluded from early release. Id. at 53691, 28 C.F.R. § 550.58 (a)(l)(vi)(B).

The Gavis Group claimed that the Bureau exceeded its authority when it adopted that position. The district court *1218 agreed. See Gavis I, 28 F.Supp.2d at 1266-67. Of course, if that is so, the Bowen Group would also be entitled to relief. For its part, however, the Bowen Group specifically asserted that the Bureau exceeded its authority because it retroactively applied that position to the members of the group. Each had previously received a provisional favorable eligibility determination, but had not yet entered the program. Again, the district court agreed. See Bowen I, 22 F.Supp.2d. at 1135. These appeals followed.

III. JURISDICTION AND STANDARDS OF REVIEW

The district court had jurisdiction pursuant to 28 U.S.C. § 2241 . We have jurisdiction pursuant to 28 U.S.C. §§ 1291 & 2253(a).

We review the district court’s grant or denial of a writ of habeas corpus de novo. See Downey, 100 F.3d at 663-64 . However, this case involves the interpretation of a statute by the Bureau, and that presents slightly different considerations. As we have said:

Tang v. Reno, 77 F.3d 1194 , 1196-97 (9th Cir.1996) (citations omitted). Moreover, those strictures still have force when “the Bureau’s interpretation appears only in a ‘Program Statemen[t]’ — an internal agency guideline — rather than in ‘published regulations subject to the rigors of the Administrative Procedure] Act, including public notice and comment.’ ” Reno v. Koray, 515 U.S. 50, 61 , 115 S.Ct. 2021, 2027 , 132 L.Ed.2d 46 (1995). As the Supreme Court has said, “BOP’s internal agency guideline, which is akin to an ‘interpretive rule’ that ‘do[es] not require notice and comment,’ is still entitled to some deference, since it is a ‘permissible construction of the statute.’ ” Id. (citations omitted); see also McLean v. Crabtree, 173 F.3d 1176, 1184 (9th Cir.1999), ce rt. denied, — U.S. -, 120 S.Ct. 814 , 145 L.Ed.2d 685 (2000).

IV. DISCUSSION

As we have already suggested, the first question before us is whether the Bureau’s interpretation is invalid, and only then need we consider whether it was applied to the Bowen Group retroactively. The Gav-is Group cannot make the retroactive claim because its members had not received any form of acceptance into a substance abuse treatment program at the time the Bureau’s interpretation was adopted.

The reversal of the district court’s order with respect to the Gavis Group requires us also to address whether the Bureau’s rule change can be applied retroactively to the members of the Bowen Group. Our decision in Cort v. Crabtree, 113 F.3d 1081 (9th Cir.1997), compels the conclusion that the exclusion of the Bowen Group from early release eligibility has an impermissible retroactive effect.

A. Validity of Interpretation

The district court was of the opinion that the Bureau could not adopt its present position because we had ruled that *1219 the Bureau was in error when it attempted to rest adoption of that position on an interpretation of “nonviolent offense.” See Gavis I, 28 F.Supp.2d at 1266-67. With all due respect, the conclusion simply does not follow from the premise.

It is clear enough that the Bureau could not go on construing the phrase “nonviolent offense” in a manner contrary to our prior rulings. See Neal v. United States, 516 U.S. 284, 294-95 , 116 S.Ct. 763, 768-69 , 133 L.Ed.2d 709 (1996); NLRB v. Ashkenazy Property Management Co., 817 F.2d 74, 75 (9th Cir.1987). But the Bureau did not do that at all. Once it was foreclosed from a simple interpretation of the statute, it, instead, exercised the discretion that Congress indisputably conferred upon the Director and reached the same conclusion on an entirely different ground. It can hardly be doubted that “an agency is free on remand to reach the same result by applying a different rationale.” Arizona Electric Power Cooperative, Inc. v. United States, 816 F.2d 1366, 1373 (9th Cir.1987). Our prior decisions could have “held no more and no less than that the [Bureau’s] first [position] was unsupportable for the reasons supplied by that agency.” SEC v. Chenery Co., 332 U.S. 194, 200 , 67 S.Ct. 1575, 1579 , 91 L.Ed. 1995 (1947). Here, the Bureau relied on an entirely different part of the statute for its decision. We see nothing sinister in that.

There can be little doubt that the Bureau has “broad discretion in administering the sentence reduction treatment program.” McLean, 173 F.3d at 1184 . That discretion extends to the creation of categorical exclusions. See id.; Jacks v. Crabtree, 114 F.3d 983, 986 (9th Cir.1997), cert. denied, 523 U.S. 1009 , 118 S.Ct. 1196 , 140 L.Ed.2d 325 (1998). No doubt, the exercise must be reasonable, but we see nothing unreasonable in the Bureau’s making the common-sense decision that there is a significant potential for violence from criminals who carry, possess or use firearms while engaged in their felonious employment, even if they have wound up committing a nonviolent offense this time. Cf. Bush v. Pitzer, 133 F.3d 455, 458 (7th Cir.1997) (upholding categorical release denial to those whose crimes present a serious potential risk of physical force against another). Congress did not say that the Bureau could not reach that conclusion. It did say that the Bureau could not grant a reduction to those whose current crime of conviction was a violent offense, but that is quite a different matter.

Finally, this is not a case of Bureau tergiversation; the Bureau has always been of the firm belief that the sort of criminal of which the members of the Bowen Group and the Gavis Group are representative should not be entitled to a reduction. But even if the Bureau had shifted its position, that would not necessarily mean that we should look askance at its current position. See NLRB v. Local Union No. 103, International Ass’n of Bridge Workers, 434 U.S. 335, 351 , 98 S.Ct. 651, 660-61 , 54 L.Ed.2d 586 (1978); Montana Power Co. v. EPA, 608 F.2d 334 , 347 (9th Cir.1979). But see Oregon v. BLM, 876 F.2d 1419, 1425 (9th Cir.1989). At any rate, there was no vacillation here; there was only the valid use of a separate provision of the statute to reach the same result. Other courts agree with our position.

Thus, in Bellis v. Davis, 186 F.3d 1092 (8th Cir.1999), petition for cert. filed, _U.S.L.W_(U.S. Dec. 15, 1999) (no. 99-7558), the court was presented with a claim that the BOP position which we deal with here was improper. The Eighth Circuit had previously ruled that the provision which limits relief to nonviolent offenders could not be used to exclude those who possessed a weapon while committing an offense. See id. at 1095. The court did not see that as relevant because, as it said, “[w]e did not, however, address the question at issue in this appeal, namely, whether the BOP may, as an exercise of its discretion, look to sentencing factors in deciding which individuals amongst statutorily eligible inmates are appropriate candidates for early release.” Id. at 1095 *1220 (citation omitted). It stated that the BOP did, in fact, have that discretion. See id. at 1094. Moreover, it opined:

Id. at 1094-95 (citations omitted); see also LaSorsa v. Menifee, 10 F.Supp.2d 316, 317 (S.D.N.Y.1998) (although BOP cannot use “nonviolent offense” language to preclude release, it can categorically exercise discretion to do so), affirmed, 182 F.3d 900 (2nd Cir.1999) (table); cf. Bush, 133 F.3d at 458 (a prisoner whose offense was nonviolent, but whose underlying conduct was prone to violence, may be excluded). Just so!

In fine, we do at least owe some deference to the Bureau’s interpretation of the statute in a way that allowed it to exercise its discretion to categorically refuse to reduce the custody time of armed felons. Because its exercise of that discretion was both permissible and reasonable, we defer to it and hold that the Bureau’s discretion was validly exercised.

B. Retroactive Application

Because we hold that the Bureau may under its discretionary authority categorically exclude felon firearm possessors from early release eligibility, we must determine whether the application of the rule change to the Bowen Group is impermissi-bly retroactive. In this case, the district court correctly concluded that the Bureau wrongfully disrupted the Bowen Group’s settled expectations because they had already been provided with a determination of eligibility prior to the date the amended regulation became effective. Therefore, under Cort , the regulation has impermissible retroactive effect.

In Cort , we applied the bedrock principle that “retroactivity is not favored in the law” to determine whether the Bureau could deny early release eligibility to inmates based on drug abuse treatment program changes implemented after the inmates had already been notified that they were eligible for early release. Cort, 113 F.3d at 1084 (quoting Bowen v. Georgetown Univ. Hospital, 488 U.S. 204, 208 , 109 S.Ct. 468 , 102 L.Ed.2d 493 (1988)). Because the “settled expectations [of inmates] should not be lightly disrupted,” Landgraf v. USI Film Products, 511 U.S. 244, 265 , 114 S.Ct. 1483 , 128 L.Ed.2d 229 (1994), we held that the program change could not be applied “to prisoners already in the treatment program on the date of its adoption, much less to prisoners who have already been found to be eligible.” See Cort, 113 F.3d at 1086-7 . Three considerations were prominent in our decision. We noted first that the language of the change notice provided no indication that the program change was to be applied retroactively. See id. It was also clear that the Bureau intended to render a binding final decision of early release eligibility, subject only to the completion of the 500-hour drug abuse treatment program. See id. at 1085 . Finally, we rejected as irrelevant the Bureau’s contention that it could freely change its eligibility determination because it retained discretion under the statute to grant or deny a sentence reduction even after an inmate completed the treatment program. See id.

*1221 Despite the Bureau’s assertions to the contrary, these reasons apply with equal force to the Bowen Group inmates. The language of both the Federal Register notice and Program Statement 5162.04 makes no indication that the regulatory and program changes were to be applied retroactively to inmates already notified of their eligibility for early release. Also, as in Cort , the Bureau continues to treat its eligibility notification as a binding “decision” which can be appealed through an administrative remedy procedure, rather than a temporary recommendation. See Cort, 113 F.3d at 1085 . Moreover, the Bureau’s contention that it retains discretion under the statute to grant or deny a sentence reduction remains irrelevant for the purposes of this appeal. Rather, the sole question is whether the Bureau must still consider the inmates’ request for early release, having already notified them of their eligibility.

The Bureau argues that the insertion of the phrase “this eligibility is provisional and may change” in each of the eligibility notices given to the Bowen Group inmates establishes that they could not have had any settled expectations of early release eligibility. It — and the dissent — point to the various definitions of the term “provisional” as “temporary” or “conditional” or “existing or serving until permanently or properly placed” to support their contention that the import of the notices was made clear to the inmates. See Black’s Law Dictionary 1102 (5th ed.1979); Webster’s Third New International Dictionary 1827 (1981); The Random House College Dictionary 1065 (revised ed.1982).

In determining the meaning given to the term “provisional” in the early release eligibility notices, however, we need not look to its dictionary definition. Cf. U.S. v. Mohrbacher, 182 F.3d 1041, 1047 (9th Cir.1999). In section 6.3 of the change notice, which enumerates the requirements for providing an inmate with notice of early release eligibility, the Bureau underscores that the term “provisional” refers only to the successful completion of all phases of the drug abuse treatment program:

Change Notice CN-03 to Program Statement 5330.10, at 7 (Oct. 9, 1997). The Bureau further states that an inmate may lose his early release eligibility only for failure to complete the treatment program. 5 The Bureau makes no indication that it intended the term “provisional” to apply to any changes in the law or new rules or regulations.

The record further supports the conclusion that the insertion of the term “provisional” in the residential drug abuse treatment program contract did not alter the Bureau’s long-held policy that early release eligibility was conditioned only upon successful completion of the treatment program. 6 See Cort, 113 F.3d at 1085 (inmates eligible for sentence reduction subject only to successful completion of program). As such, it is clear that, even with the addition of the term “provisional,” *1222 the eligibility determination is contingent only upon completion of the program, and not on any changes in the law or regulations.

The Bureau’s contention that Cort is distinguishable because it dealt with inmates who had both received a favorable eligibility determination program and entered the drug treatment program falls short. The Bureau asserts that none of the members of the Bowen Group could have had any settled expectations of early release eligibility because they had merely been notified of early release eligibility, but had not entered a treatment program in reliance on their notification of early release eligibility. Our decision in Fur-guiel v. Benov, 155 F.3d 1046, 1048 (9th Cir.1998), settles this question.

In Furguiel, we considered whether an inmate who had entered a treatment program without being notified by the Bureau that he was eligible for early release had a settled expectation of being eligible for early release. See id. Presumably, in such a circumstance, without more, a prisoner could have enrolled in the program because of his desire to rid himself of his drug addiction. The critical ingredient in resolving this question therefore was whether the inmate had been notified of early release eligibility. We held that “a prisoner’s expectation of early release may only arise when the BOP makes a lawful determination of the prisoner’s eligibility and then informs the prisoner of such eligibility.” Id. at 1049 . Thus, all that is required under our case law is that “a prisoner’s notice of eligibility for early release must have accrued prior to the promulgation of § 550.58,” as is the case in the instant appeal. See id.

The early release incentive program is an important part of Congress’s effort to reduce recidivism by encouraging féderal prisoners to participate in drug treatment programs. The programs require a substantial commitment by the inmate and the institution. Thus far, the programs have been successful. However, this is not a game of Lucy and the football from the world of Charles Schulz. Rather, it is a serious administrative agency program to be administered in a consistent, coherent matter. An agency cannot provide participants with a determination of eligibility based on the purported examination of objective criteria, then subsequently deny them eligibility by exercise of whim. If we expect inmates to observe the rule of law, we must adhere to it ourselves.

In sum, the BOP impermissibly applied its rule changes to the Bowen Group inmates in violation of the retroactivity doctrine after notifying them of their eligibility for early release. We further conclude that the district court did not abuse its discretion in modifying its original order pursuant to Federal Rule of Civil Procedure 60(a) to require that the Bowen Group inmates successfully complete all phases of the drug abuse treatment program before being entitled to the one-year sentence reduction.

V. CONCLUSION

A.

When the Director of the Federal Bureau of Prisons determined that he would exercise his discretion to categorically exclude prisoners who had possessed, carried or used firearms while they committed their felonies, that was no mere contretemps. Nor was it an administrative bou-leversement directed toward overturning our ultimate authority to declare what the law is. It was, instead, a decision made pursuant to a longstanding opinion of the Bureau that “such men are dangerous,” regardless of whether they think too much. 7 The decision to act was both reasonable and within the authority conferred upon the Bureau by Congress. We defer to that exercise of discretion, and uphold the determination, even though we did disapprove of an earlier attempt to reach the same result by a different path. There *1223 fore we reverse as to the members of the Gavis Group.

B.

We, however, affirm the determination of the district court that the categorical exclusions cannot be applied to the members of the Bowen Group. Having been notified by the Bureau that they would be eligible for early release consideration, the members of the Bowen Group clearly had settled expectations of early release eligibility. The Bureau cannot now take away with its left hand what it has already given with its right. AFFIRMED, as to the Bowen Group members; REVERSED, as to the Gavis Group members.

. See Gavis v. Crabtree, 28 F.Supp.2d 1264 (D.Or.1998) (Gavis I); Bowen v. Crabtree, 22 F.Supp.2d 1131 (D.Or.1998) (Bowen I).

. The Gavis Group consists of John Gavis, Conrad Niemeier, Harold T. Gray, Douglas J. Gregg, Ruben Castillo, Sabil M. Mujahid, Robert W. Curley, Gary Lee Southwick, Patrick A. Hansen, Robert Knaeble, Karlos Lamar Grier, Daniel Lee Williams, Richard Lightbourne, Darren W. Williams, Edward Wills, James Darmiento, Scott Alan DeCham-beau, Vincente Subia, Daniel Frederic Ramos, Warren Katz, Darrell L. Johnson, Brett Warden, Delbert Duane Young, and Michael J. Marshall.

.The Bowen Group consists of Paul A. Bowen, Austin David Buckley, John Peter Goulet, William Dale Hollingsworth, Lance Austin Jones, Wallace Ward Payne, Donald Scott, Guy D. Taketa, Ovid John Teixeira, Lamar Tollivar and Steven Winkelman.

. Loss of Provisional Early Release. An inmate may lose his or her provisional early release at any time for failure to successfully complete all components of the drug treatment program (including transitional services), or for committing certain prohibited acts.

. Mary Sullivan, an executive assistant for the Bureau, stated in a facsimile that "[t]he major change is the addition of the § re: 'eligibility is provisional' (CN-01, .B3.P3) Although not in first [contract], this has always been the case.”

. William Shakespeare, Julius Caesar act 1, sc. 2.