TATEL, Circuit Judge:

A former District of Columbia prisoner appeals the district court’s sua sponte dismissal of his 42 U.S.C. § 1983 complaint. Claiming due process and equal protection violations by prison officials who had allegedly miscalculated his parole eligibility date, misclassified him as a felon, and barred him from participating in certain 'prison programs, the prisoner sought damages as well as injunctive relief. Appellees argue that he should have brought his parole eligibility claims in habeas corpus, but since those claims, if successful, would not have automatically resulted in his speedier release, we conclude that he properly brought them pursuant to section 1983. Because we also find that the prisoner’s pro se claim that he was denied access to prison programs on the basis of his race or ethnicity was sufficient to survive sua sponte dismissal, we remand that claim for further proceedings. We affirm the district court’s dismissal of his other claims.

Appellant Kingsley Anyanwutaku, a landlord operating in the District of Columbia, pleaded guilty to numerous misdemeanor violations of D.C.’s housing, building, zoning, licensing, and tax codes. The D.C. Superior Court sentenced him to multiple consecutive sentences .totaling over six years.

While in the custody of the D.C. Department of Corrections, Anyanwutaku filed a confusing pro se complaint in U.S. District Court for the District of Columbia against the Department and various Department officials under 42 U.S.C. §■ 1983 (1994). Seeking correction of his parole eligibility records, compensatory and punitive damages, and prospective injunctive relief, his complaint alleges that he was “entitled to a timely parole classification date within 60 days of incarceration or at least much sooner than 10/25/97 as recorded and maintained by the record office.” Compl. at 6-7. The complaint also claims that the Department’s refusal to correct his “parole classification date” deprived him of due process and equal protection. Id. at 7-8. In five inmate grievance forms and one informal written grievance attached to his complaint, Anyanwutaku alleges that he was denied a timely parole eligibility hearing; in two of these documents, he claims prison officials denied him access to educational, religious, and other prison programs. Id. at 13-20.

Anyanwutaku sought to proceed in forma pauperis, but the district court never ruled on his application. Instead, on the same day Anyanwutaku filed his complaint, the district court, finding no constitutional right to parole, sua sponte dismissed it under “28 U.S.C. § 1915(d)”; we assume the district court meant section 1915(e), 28 U.S.C.A. § 1915(e) (Supp.1998), with which the Prison Litigation Reform Act of 1996, Pub.L. No. 104-134, 110 Stat. 1321 (1996), replaced former section 1915(d). Anyanwutaku then filed a motion for reconsideration, later filing an “addendum” to the motion. Together, these documents clarify Anyanwutaku’s original complaint as alleging two primary claims: that prison officials denied him due process by miscalculating his parole eligibility date, by misclassifying him as a felon, and by failing to correct both errors, thus delaying his eligibility for parole; and that on the basis of his race or ethnicity, prison officials denied him access to prison programs that would have advanced his opportunity to obtain parole at an earlier date. One other *1055 possible claim emerges from these documents: that prison officials miscalculated An-yanwutaku’s parole eligibility date and mis-elassified him as a felon because of his race or ethnicity. Reaffirming its section 1915(e) dismissal, the district court denied the motion for reconsideration.

Anyanwutaku now appeals the denial of the motion for reconsideration. The district court granted his application to proceed in forma pauperis on appeal. We appointed counsel for Anyanwutaku and scheduled oral argument together with two other prison litigation cases whose opinions we also issue today: Blair-Bey v. Quick, No. 96-5280, slip op., 1998 WL 412488 (D.C.Cir. July 24,1998), and Crowell v. Walsh, No. 96-7192, slip op., 1998 WL 412489 (D.C.Cir. July 24, 1998). We directed the parties to address whether the PLRA’s filing fee requirement, 28 U.S.C. § 1915(b), applies to this case, and whether Anyanwutaku must obtain a certificate of appealability pursuant to 28 U.S.C. § 2253, as amended by the Antiterrorism and Effective Death Penalty Act of 1996 (“AEDPA”), Pub.L. No.104-132, 100 Stat. 1214 (1996). While this appeal was pending, the D.C. Board of Parole released Anyanwutaku on parole.

Because In re Smith, 114 F.3d 1247, 1250 (D.C.Cir.1997), makes clear that Anyanwuta-ku’s appeal falls squarely within the ambit of the PLRA’s filing fee requirements, we ordered Anyanwutaku to pay the necessary fee before we would consider the remaining issues in his case. Anyanwutaku v. Moore, No. 96-7259 (D.C.Cir. June 18, 1998). He has now made that payment, so his appeal is properly before us.

We begin with a few threshold issues: Did Anyanwutaku need to bring his challenges to his parole eligibility date in habeas? Did he need to obtain a certificate of appealability pursuant to the newly enacted AED-PA? What effect does his release have on the justiciability of his claims?

As to the first issue, appellees contend that Anyanwutaku should have brought his challenges to his parole eligibility date not under section 1983, but as a petition for habeas corpus, and that because Anyanwutaku failed to exhaust his local habeas remedy, the district court lacked jurisdiction over his claims. We disagree.

Starting with Preiser v. Rodriguez, 411 U.S. 475, 93 S.Ct. 1827, 36 L.Ed.2d 439 (1973), the Supreme Court has carved out a category of prisoner cases challenging the “fact or duration” of confinement that sound exclusively in habeas. Id. at 500, 93 S.Ct. 1827. In Preiser, state prisoners brought actions under section 1983 seeking restoration of good time credits that they lost as a result of adyerse disciplinary actions, actions the prisoners claimed deprived them of due process.. Holding that the prisoners must bring their claims in habeas, the Supreme Court noted that “even if restoration of respondents’ good-time credits had merely shortened the length of their confinement, rather than required immediate discharge from that confinement, their suits would still have been within the core of habeas corpus in attacking the very duration of their physical confinement itself.” Id. at 487-88, 93 S.Ct. 1827. Such cases, the Court said, must take the form of habeas petitions exclusively because 28 U.S.C. § 2254(b) “require[s] exhaustion of adequate state remedies as a condition precedent to the invocation of federal judicial relief.... It would wholly frustrate explicit congressional intent to hold that the respondents in the present case could evade this requirement by the simple expedient of putting a different label on their pleadings.” Id. at 489-90, 93 S.Ct. 1827.

Unlike the prisoners in Preiser, whose challenges to the loss of good time credits, if successful, would have automatically shortened the duration of their confinement, Any-anwutaku challenges his assigned parole eligibility date. Although Anyanwutaku would have been eligible for parole at an earlier date had he prevailed on his claims in the district court, because D.C. parole decisions are entirely discretionary, see D.C.Code Ann. § 24-204(a) (1996), there is no guarantee that he would have been released any earlier. Interpreting Preiser, a majority of our sister circuits have held that challenges to state parole procedures whose success would not *1056 necessarily result in immediate or speedier release need not be brought in habeas corpus, even though the prisoners filed their suits for the very purpose of increasing their chances of parole. See, e.g., Gwin v. Snow, 870 F.2d 616, 624-25 (11th Cir.1989); Serio v. Members of La. State Bd. of Pardons, 821 F.2d 1112, 1119 (5th Cir.1987); Georgevich v. Strauss, 772 F.2d 1078, 1087 (3d Cir.1985) (en banc); Walker v. Prisoner Rev. Bd., 694 F.2d 499, 501 (7th Cir.1982); Candelaria v. Griffin, 641 F.2d 868, 869 (10th Cir.1981) (per curiam); Strader v. Troy, 571 F.2d 1263, 1269 (4th Cir.1978); Williams v. Ward, 556 F.2d 1143, 1150-51 (2d Cir.1977). Even the Supreme Court reached the merits of a section 1983 claim by state prisoners alleging due process violations in the consideration of their suitability for parole without first addressing whether Preiser required the claim to be brought in habeas. See Greenholtz v. Inmates of the Neb. Penal and Correctional Complex, 442 U.S. 1, 99 S.Ct. 2100, 60 L.Ed.2d 668 (1979).

The Supreme Court’s recent decisions in Heck v. Humphrey, 512 U.S. 477, 114 S.Ct. 2364, 129 L.Ed.2d 383 (1994), and Edwards v. Balisok, 520 U.S. 641, 117 S.Ct. 1584, 137 L.Ed.2d 906 (1997), underscore the distinction between this case and Preiser. In Heck, a state prisoner sought section 1983 damages, claiming that he had been unlawfully convicted and sentenced. Although he requested neither release from prison nor in-junctive relief, the Court held that his claim had to be brought in habeas because, in effect, it amounted to a collateral attack on his conviction, since in order to prevail he had to “prove the unlawfulness of his conviction or confinement.” Heck, 512 U.S. at 486, 114 S.Ct. 2364. The Court thus held that:

when a state prisoner seeks damages in a § 1983 suit, the district court must consider whether a judgment in favor of the plaintiff would necessarily imply the invalidity of his conviction or sentence; if it would, the complaint must be dismissed unless the plaintiff can demonstrate that the conviction or sentence has already been invalidated. But if the district court determines that the plaintiffs action, even if successful, will not demonstrate the invalidity of any outstanding criminal judgment against the plaintiff, the action should be allowed to proceed, in the absence of some other bar to the suit.

Id. at 487, 114 S.Ct. 2364. In Balisok, a state prisoner brought a section 1983 action alleging that his disciplinary proceeding was tainted by deceit and bias — a procedural defect so severe that in the Court’s view the only available remedy was reinstatement of the good time credits that had been deducted as a result of the proceeding. Applying Heck’s reasoning, the Court held that the claim had to be brought in habeas because, if successful, it would “necessarily imply” the invalidity of the loss of good time credits. Balisok, 117 S.Ct. at 1588-89.

We read these cases to require that a state prisoner’s section 1983 claim must first be brought in habeas only when, if successful; it would “necessarily imply,” or automatically result in, a speedier release from prison. As the Ninth Circuit explained in ruling that prisoners’ claims that they were improperly labeled sex offenders, thus affecting their parole eligibility, were properly brought under section 1983,

[t]he only benefit that a victory in this case would provide [the prisoners], besides the possibility of monetary damages, is a ticket to get in the door of the parole board, thus only making them eligible for parole consideration.... If [they] win, it will in no way guarantee parole or necessarily shorten their prison sentences by a single day.

Neal v. Shimoda, 131 F.3d 818, 824 (9th Cir.1997). Anyanwutaku faces precisely the same situation. Had he succeeded in the district court, he would have earned nothing-more than a “ticket to get in the door of the parole board.” He thus properly brought his claim under section 1983.

Contrary to appellees’ contention, neither Best v. Kelly, 39 F.3d 328 (D.C.Cir.1994), nor Chatman-Bey v. Thornburgh, 864 F.2d 804 (D.C.Cir.1988) (en banc), requires a different result. Like Preiser, Best involved prisoner challenges to the loss of good time credits through the cancellation of a drug treatment program; if successful, their claims, unlike *1057 Anyanwutaku’s, would have necessarily resulted in speedier release.- 39 F.3d at 330. Chatman-Bey, which required parole eligibility challenges to be brought in habeas, dealt expressly with federal prisoners, see 864 F.2d at 809, 810 n. 6; because Anyanwutaku was in the custody of the District of Columbia, we need not decide whether Chatman-Bey has any continuing vitality after Heck and Bali-sok

Our conclusion that Anyanwutaku properly brought all of his claims under section 1983 not only means that he had no state remedies to exhaust, but also answers the question whether Anyanwutaku needed to obtain a certificate of appealability under the AEDPA to maintain his appeal. He did not. The AEDPA’s certificate of appealability requirement applies only to appeals from “the final order in a habeas corpus proceeding in which the detentiqn complained of arises out of process issued by a State court,” 28 U.S.C.A. § 2253(c)(1)(A), and “the final order in a proceeding under section 2255,” id. § 2253(c)(1)(B), not to section 1983 actions.

This brings us to the final preliminary question raised by this case: Are Anyanwutaku’s claims any longer justiciable in view of his release from prison? The constitutional “ ‘case-orcontroversy requirement subsists through all stages of federal judicial proceedings, trial' and appellate.... The parties must continue to have a personal stake in the outcome of the lawsuit.’”' Spencer v. Kemna, - U.S.-,-, 118 S.Ct. 978, 983, 140 L.Ed.2d 43 (1998) (quoting Lewis v. Continental Bank Corp., 494 U.S. 472, 477-78, 110 S.Ct. 1249, 108 L.Ed.2d 400 (1990)). Accordingly, when a prisoner seeking injunctive or declaratory relief challenges his parole eligibility date but is subsequently released on parole, his claims are moot unless he alleges continuing adverse consequences from the challenged parole records. See Kerr v. Farrey, 95 F.3d 472, 476 (7th Cir.1996) (holding that a paroled prisoner’s claim to have negative references about his attendance at a prison program expunged from his prison records was not moot “because any such references may have a continuing adverse impact "on him”); cf Spen’cer, at-, 118 S.Ct. at 983 (challenge to parole revocation by prisoner who has since been re-released requires that “continuing ‘collateral consequences’ of the parole revocation be either proven or presumed”). Anyanwutaku has nowhere explained what adverse impact he continues to suffer as a result of the Parole Board’s alleged failure to give him a timely parole eligibility date, and we can think of none. His release on parole thus rendered moot his claims for correction of his parole eligibility records and for prospective injunctive relief. See Chatman-Bey, 864 F.2d at. 805 (explaining that a prisoner’s challenge to his parole eligibility date in In re U.S. Parole Commission, 793 F.2d 338 (D.C.Cir.), reh’g granted and opinion vacated, 798 F.2d 1532 (D.C.Cir.1986), was eventually dismissed as moot upon prisoner’s release on parole). His damages claims, however, remain properly before us. See Smith, 114 F.3d at 1249; Kerr, 95 F.3d at 476.

Ill

Turning to the merits of Anyanwutaku’s appeal', we find nothing in the record indicating whether he filed his pro se motion for reconsideration pursuant to Rule 59(e) or Rule 60(b) of the Federal Rules of Civil Procedure. We treat the motion as having been filed under Rule 59(e), in. light of several considerations: The district court appears-to have treated it as a Rule 59(e) motion; Anyanwutaku filed it pro se; appellees failed to raise the issue; and Anyanwutaku may have filed it within the ten days required by Rule 59(e). (Although the record does not indicate, when he gave his motion to prison officials for delivery to the district court, the key date .under the “mailbox rule” for pro se prisoner pleadings, see, e.g., Houston v. Lack, 487 U.S. 266, 270-71, 108 S.Ct. 2379, 101 L.Ed.2d 245 (1988), since the district court received the motion seventeen days after it dismissed the complaint, see Fed. R. Civ. P. 6(a) (computation of time), Anyanwutaku could well have given it to prison officials within ten days.)

Rule 59(e) motions “need not be granted unless the district court finds that there is an ‘intervening change of controlling law, the availability of new evidence, or the *1058 need to correct a clear error or prevent manifest injustice.’ ” Firestone v. Firestone, 76 F.3d 1205, 1208 (D.C.Cir.1996) (per cu-riam) .(quoting National Trust for Historic Preservation v. Department of State, 834 F.Supp. 453, 455 (D.D.C.1993), affd in part and rev’d in part on other grounds sub nom. Sheridan Kalorama Historical Ass’n v. Christopher, 49 F.3d 750 (D.C.Cir.1995)). We review district court denials of Rule 59(e) motions for reconsideration for abuse of discretion. Id.

In in forma pauperis proceedings, section 1915(e) requires district courts to dismiss “frivolous or malicious” actions, 28 U.S.C.A. § 1915(e)(2)(B)(i), actions that “fail[ ] to state a claim on which relief may be granted,” id. § 1915(e)(2)(B)(ii), and actions that “seek monetary relief against a defendant who is immune from such relief,” id. § 1915(e)(2)(iii). The district court never said which of these deficiencies provided the basis for dismissal. But because in both the order dismissing the complaint and the order denying the motion for reconsideration the district court pointed out that prisoners have no constitutional right to parole, we assume that the district court dismissed the. complaint either because it failed to state a claim or because it was frivolous.

According to appellees, Anyanwutaku’s contention that he was discriminatorily prohibited from participating in certain prison programs failed to state a claim because he has not “shown” the two necessary predicates to an equal protection claim, i.e., that he was treated differently from others similarly situated, and that prison officials acted with intent to disadvantage him relative to others. Appellees demand too much. An in forma pauperis complaint may be dismissed sua sponte for failure to state a claim only if “ ‘it appears beyond doubt that the plaintiff can prove no set of facts in support of his claim which would entitle him to relief.’ ” Baker v. Director, 916 F.2d 725, 726 (D.C.Cir.1990) (per curiam) (quoting Conley v. Gibson, 355 U.S. 41, 45-46, 78 S.Ct. 99, 2 L.Ed.2d 80 (1957)). At this early stage, where the complaint constitutes the only submission before the district court, the complaint need only be “sufficiently plausible that the claim could state a cause of action.” Brandon v. District of Columbia Bd. of Parole, 734 F.2d 56, 61 (D.C.Cir.1984). To be sure, Anyanwutaku’s complaint is confusing and fails to explain clearly that his allegations about the prison programs relate to his equal protection claims. But in his motion for reconsideration, he says quite specifically that he was “arbitrarily and capriciously denied access to the said [prison] programs through invidious discrimination,” and then two sentences later he says that “the defendants invidiously discriminated against the plaintiff based on race or ethnic origin.” Given that we “liberally eonstrue[ ]” pro se prisoners’ pleadings, see Estelle v. Gamble, 429 U.S. 97,106, 97 S.Ct. 285, 50 L.Ed.2d 251 (1976), holding them, “however inartfully pleaded,” to “less stringent standards” than pleadings drafted by counsel, Haines v. Ker-ner, 404 U.S. 519, 520, 92 S.Ct. 594, 30 L.Ed.2d 652 (1972) (per curiam); see also United States v. Sanchez, 88 F.3d 1243,1247 (D.C.Cir.1996), we believe that this allegation was sufficient to plead a section 1983 cause of action. The district court should have allowed it to proceed beyond the sua sponte dismissal stage. Cf. Moore v. Agency for Int’l Dev., 994 F.2d 874, 877 (D.C.Cir.1993) (holding that district court should have permitted plaintiff to amend his complaint because the Tong-standing principle that “leave to amend a complaint shall be freely given when justice so requires ... would appear to be particularly appropriate when the party seeking to amend is permitted to proceed in forma pauperis and, because of his circumstances, does so without benefit of counsel”) (internal quotations and citations omitted).

Nor do we think, at least at this early stage of the litigation, that Anyanwutaku’s claim can be considered frivolous, i.e., that it rests on a “ ‘fanciful factual allegation,’ ” Johnson v. Gibson, 14 F.3d 61, 63 (D.C.Cir.1994) (per curiam) (quoting Neitzke v. Williams, 490 U.S. 319, 325, 109 S.Ct. 1827, 104 L.Ed.2d 338 (1989)). We recognized the viability of a section 1983 claim similar to Anyanwutaku’s in Women Prisoners of the D.C. Department of Corrections v. District of Columbia, 93 F.3d 910, 924 (D.C.Cir.1996), where we concluded that allegations that the Department discriminated against the pris *1059 oners on the basis of sex as to prison programs and services made out a cognizable equal protection claim. Even if Anyanwuta-ku might lose on the merits, we think the district court should have permitted his claim, drafted pro se and based on legitimate factual allegations, to proceed.

Accordingly, the district court’s refusal to reconsider its sua sponte dismissal of Anyanwutaku’s prison programs equal protection claim amounted to an abuse of discretion. The court’s dismissal of Anyanwutaku’s remaining claims did not. With regard to Anyanwutaku’s claim that he was denied due process because he was entitled to be considered or “classified” for parole within sixty days of his incarceration, and was not so classified because he was misclassified as a felon, Anyanwutaku has failed to allege that he has been deprived of a protected liberty interest, the first element of any due process claim. D.C. law creates no liberty interest in a parole eligibility date, much less one within sixty days of incarceration, since misdemeanants must serve one-third of their aggregate sentences before being considered for parole, see D.C.Code Ann. § 24-208(a).

Finally, nothing in either Anyanwutaku’s complaint or his motion for reconsideration sufficiently sets forth any independent equal protection claim with regard to his parole eligibility. His motion for reconsideration merely states that his parole eligibility date is “wrong and is arbitrarily and capriciously prolonged.” Neither his motion for reconsideration nor his complaint directly tied that claim — in contrast to his prison programs equal protection claim — to any allegations of discrimination based on race or ethnicity, or any other specific type of equal protection violation. Accordingly, because it was not “sufficiently plausible that [Anyanwutaku’s] claim could state a cause of action,” Brandon, 734 F.2d at 61, the district court’s dismissal did not amount to an abuse of discretion.

We reverse the district court’s denial of the motion for reconsideration with respect to Anyanwutaku’s prison programs equal protection claim and remand for further proceedings. In all other respects, we affirm.

' So ordered.