OPINION OF THE COURT
WEIS, Circuit Judge.In this case, a state prisoner alleges that he was denied parole in retaliation for the successful pursuit of relief in various federal habeas corpus proceedings. The district court denied the petition on the merits and also found a failure to exhaust “administrative” remedies.1 Because we conclude that petitioner has failed to exhaust state remedies, and in addition, that some uncertainty exists as to the proper state procedure to address the issue that the prisoner raises, we remand with directions to dismiss.
Between February 1981 and April 1982, the district attorney of Blair County, Pennsylvania, filed three sets of charges against petitioner Wayne Burkett. In November 1981, he was convicted of burglary, theft, receiving stolen property, and corruption of minors, docketed in 1981 at Nos. 140/141. On January 20, 1982, Burkett was convicted of rape, involuntary deviate sexual intercourse, terroristic threats, unlawful restraint, *137indecent exposure, reckless endangerment, indecent assault, and aggravated assault, docketed in 1981 at No. 161. A third conviction, entered on January 28, 1983 for attempted rape, terroristic threats, assault, and reckless endangerment was docketed in 1982 at No. 284.
In an earlier proceeding, we granted habe-as corpus relief resulting in the vacation of the convictions at Nos. 140/141 and 161 because of inordinate delays in sentencing. See Burkett v. Cunningham, 826 F.2d 1208 (3d Cir.1987). In Burkett v. Fulcomer, 951 F.2d 1431 (3d Cir.1991), we held that the sentence imposed at No. 284 should be reduced because of delay.
After another round of orders from the district court and this Court, the state judge denied Burkett’s motion for recusal and reduced the sentence in accordance with our earlier order. Petitioner is presently serving a term of 12% to 28% years. In February 1993, Burkett filed a Post Conviction Relief Act petition in Blair County challenging the sentence as excessive.
In September 1994, the Pennsylvania Parole Board denied petitioner’s request for parole, citing, among other reasons, “very high assaultive behavior potential” and “unfavorable recommendation from district attorney and sentencing judge.” The Board rejected petitioner’s request for reconsideration, stating: “Be advised that what the Board decides and why, with regard to parole/reparole, is wholly within the Board’s discretion and not subject to judicial review. Reider v. Pennsylvania Board of Probation and Parole, 100 Pa.Cmwlth. 333, 514 A.2d 967 (1986) (en banc).”
On September 28,1994, Burkett filed a pro se habeas corpus petition in the Pennsylvania courts raising, among other claims, retaliatory denial of parole. The state court dismissed the petition without prejudice and appointed new counsel with instructions to file an amended petition.
In June 1995, Burkett initiated the present matter by filing a document in the district court entitled “Motion to Enforce Order of the District Court Dated December 4, 1992 and to Permit Discovery in Support of Burk-ett’s Motion.” (The December 4, 1992 order had directed the imposition of a reduced sentence, as discussed in our opinion at 951 F.2d at 1433.) In this “motion,” Burkett alleged that the Commonwealth of Pennsylvania had denied him parole in vindictive retaliation for his success in the earlier federal habeas corpus actions he had pressed in the district court and our Court.
The district court denied the motion, finding inter alia that the decision to grant parole was committed to the sound discretion of the Parole Board and that the agency had cited at least five legitimate and non-discriminatory reasons for its action. Further, the court stated that the responses of the district attorney and the sentencing judge were proper and non-vindictive. In addition, the court concluded that Burkett had failed to exhaust his administrative remedies.
Burkett has appealed, contending that no corrective state process exists and therefore the district court should have conducted an evidentiary hearing and allowed discovery.
I.
Appellate Jurisdiction
Burkett’s motion in the district court was filed under the docket number of an earlier case. It should have been filed under a separate docket number rather than as a continuation of the previous action. However, because the district court and the parties have treated this case as a new petition for a writ of habeas corpus, we will do likewise. The district court’s order disposing of the matter is final as a practical matter and we have jurisdiction to consider this appeal.
II.
Exhaustion of State Remedies
State prisoners alleging a constitutional violation and improper incarceration must present their arguments to the state courts before they will be addressed by the federal courts. 28 U.S.C. § 2254(b). At the time the “motion” was filed in the district court, 28 U.S.C. § 2254(c) read: “An applicant shall not be deemed to have exhausted the remedies available in the courts of the *138State ... if he has the right under the law of the State to raise, by any available procedure, the questions presented.”
To satisfy the exhaustion requirement, the claim must be presented to the state’s highest court. Rose v. Lundy, 455 U.S. 509, 515, 102 S.Ct. 1198, 1201-02, 71 L.Ed.2d 379 (1982). “The exhaustion requirement does not foreclose, but only postpones, federal relief.” Toulson v. Beyer, 987 F.2d 984, 986 (3d Cir.1993). Pursuing state remedies is not a mere formality, but serves the interests of comity between the state and federal courts. Gibson v. Scheidemantel, 805 F.2d 135, 138 (3d Cir.1986).
After this appeal was taken, Congress enacted the Antiterrorism and Effective Death Penalty Act of 1996, Pub.L. No. 104-132, 110 Stat. 1214 (April 24, 1996), which revises the procedures for habeas corpus proceedings. Section 104(1) of the Act states that applications by persons in state custody “shall not be granted unless it appears that ... the applicant has exhausted the remedies available in the court of the State” or there is no available state remedy or that process would be ineffective. However, a federal court may deny an application on the merits notwithstanding an applicant’s failure to exhaust state remedies. Id.
The 1996 statute also provides that if a state court has addressed the merits of a petitioner’s claim, the federal court shall not grant a writ of habeas corpus unless the state decision was contrary to, or an unreasonable application of, federal law, or was based on an unreasonable determination of the facts in light of the evidence presented in the state proceeding. Section 104(3). Applicants have the burden to rebut a state’s factual determinations by clear and convincing evidence. Section 104(4). Section 104(4) also specifies the limited circumstances in which a federal court can hold an evidentiary hearing if the applicant has failed to develop the factual basis for a claim in the state proceeding.2 In the somewhat unusual circumstances here, we need not digress to determine the effect of these provisions on this pending action, filed, as it was, before the amendments were enacted.
III.
Does the State Lack Corrective Measures?
Burkett contends that retaliation for his exercise of access to the federal courts violates his rights under the United States Constitution, but that the state courts will not entertain his claim. He points to the Pennsylvania Commonwealth Court’s in banc decision in Reider v. Pennsylvania Bd. of Probation and Parole, 100 Pa.Cmwlth. 333, 514 A.2d 967 (1986).
In that case, a state prisoner appealed to the Commonwealth Court alleging that the Parole Board’s decision to deny him parole was a denial of his constitutional rights to equal protection as well as due process, and in addition constituted cruel and unusual punishment. In an opinion dismissing the appeal, the Court reviewed a number of its earlier rulings that had reached differing results on its power to review Parole Board decisions asserted to have been in violation of the Constitution.3
Because the Court’s jurisdiction to review agency decisions rests on the administrative agency law of Pennsylvania, 2 Pa. Cons.Stat. Ann. §§ 701-704, which authorizes appeals from “adjudications,” Reider looked to the statutory definition of that word. The term *139“adjudication” excludes “any order based upon a proceeding ... which involves ... paroles.” 2 Pa.Con.Stat.Ann. § 101. The Commonwealth Court concluded that “[b]y definition, therefore, Board action of denying parole is not an adjudication subject to judicial review.” Reider, 514 A.2d. at 970.
The Reider opinion acknowledged that the Pennsylvania Supreme Court in Bronson v. Pennsylvania Bd. of Probation and Parole, 491 Pa. 549, 421 A.2d 1021 (1980) had held that a prisoner could seek judicial review of a parole revocation. In distinguishing Bronson, the Commonwealth Court cited Greenholtz v. Inmates of Nebraska Penal & Correctional Complex, 442 U.S. 1, 99 S.Ct. 2100, 60 L.Ed.2d 668 (1979), which concluded that a parole revocation affected a liberty interest because the ruling returned a parolee to custody. In contrast, a prisoner denied parole is not at liberty but remains in custody and thus his status remains unchanged.
Following that reasoning, Reider held that under Pennsylvania law, a prisoner had “no constitutionally protected liberty interest in the expectation of being [paroled].” 514 A.2d at 971. “The mere possibility of parole affords no constitutional rights to prisoners.” Id. (emphasis in original). The Court, therefore, held that a denial of parole may not be judicially reviewed in Pennsylvania. A dissenting Commonwealth Court judge pointed out that carrying his Court’s holding to its logical extreme would allow the Board to refuse parole solely on the basis of a prisoner’s race, religion, gender, or ethnic background without any relief from the judiciary. Id. at 972.
Later panel opinions of the Commonwealth Court seem to indicate that it is having second thoughts about the scope of the Reider holding. Thus, in Murgerson v. Pennsylvania Bd. of Probation and Parole, 135 Pa. Cmwlth. 10, 579 A.2d 1335, 1336 n. 2 (1990), the Court commented that because the imposition of conditions is a part of the parole decision, “consistent with the rationale in Reider we hold that the imposition of such conditions is not subject to judicial review absent an allegation that the condition violates a prisoner’s constitutional rights.” (emphasis added). See also McCaskill v. Penn sylvania Bd. of Probation and Parole, 158 Pa.Cmwlth. 450, 631 A.2d 1092, 1094 n. 2 (1993) (judicial review of Parole Board’s order includes determination of whether constitutional rights were violated, citing 2 Pa. Cons.Stat.Ann. § 704).
Other cases, however, are consistent with Reider. See Shaw v. Pennsylvania Bd. of Probation and Parole, 671 A.2d 290, 292 (1996) (allegations of due process and equal protection violations do not establish “liberty interest” and claims unreviewable); King v. Pennsylvania Bd. of Probation and Parole, 111 Pa.Cmwlth. 392, 534 A.2d 150, 151 (1987) (retaliatory denial not reviewable); Johnson v. Pennsylvania Bd. of Probation and Parole, 110 Pa.Cmwlth. 142, 532 A.2d 50, 52 (1987) (due process contention not reviewable).
Reider was correct in its conclusion that no liberty interest is created by the expectation of parole. See Greenholtz, 442 U.S. at 11, 99 S.Ct. at 2105-06. But Reider is seriously flawed because it fails to recognize that the curtailment of a liberty interest is not the only way that the Constitution may be violated.
The Supreme Court held in Perry v. Sindermann, 408 U.S. 593, 597, 92 S.Ct. 2694, 2697, 33 L.Ed.2d 570 (1972), that although a person may have no “right” to a valuable government benefit, and may be denied it for any number of reasons, “there are some reasons upon which the government may not rely.” We applied that principle in Block v. Potter, 631 F.2d 233, 236 (3d Cir.1980), where we explained “[although Greenholtz indicates that a state may ... deny it completely, a state statute may not sanction totally arbitrary parole decisions founded on impermissible criteria.” Moreover, “[a] legislative grant of discretion does not amount to a license for arbitrary behavior.” Id.
In Block, the Parole Board used race as one of the bases for denying parole. The panel majority concluded that in so doing, the agency violated substantive due process in grounding its action on “constitutionally impermissible reasons.” Id. at 236. The panel also concluded that the denial of parole violated the prisoner’s right to equal protee*140tion. “The equal protection clause forbids government bodies from making decisions on the basis of race, even if other factors were also considered.” Id. at 241.
The dissenting judge in Block disagreed with the majority’s finding of a liberty interest and declined to read Greenholtz as applicable to both substantive as well as procedural due process. However, the dissent concurred with the majority’s position on equal protection and said that a discretionary parole system “does not give the state the unfettered right to deny parole on arbitrary and impermissible grounds.” Id. at 244.
Cases in other Courts of Appeals have been in agreement with Block’s premise. See Candelaria v. Griffin, 641 F.2d 868, 870 (10th Cir.1981) (denial of parole because prisoner was Hispanic states claim for violation of equal protection); Osborne v. Folmar, 735 F.2d 1316, 1317 (11th Cir.1984) (prisoner may challenge parole decisions on equal protection grounds even though he fails to establish due process claim).
state may not bar parole in retaliation for a prisoner’s exercise of his constitutional rights. See Shabazz v. Asians, 980 F.2d 1333 (10th Cir.1992) (retaliation for a prisoner’s religious discrimination suits against prison officials); Clark v. Georgia Pardons and Paroles Board, 915 F.2d 636, 639 (11th Cir.1990) (retaliation for filing suit against prison officials for wrongful death of prisoner’s brother). See also Cain v. Lane, 857 F.2d 1139, 1145 (7th Cir.1988) (retaliation for exercise of First Amendment rights). Case law has also established that a
Several Courts of Appeals have addressed analogous retaliation claims in the prison setting, although not involving parole decisions. Adams v. James, 784 F.2d 1077, 1080 (11th Cir.1986), noted that the “unconstitutional conditions” doctrine applies in prisoner section 1983 cases. Accord Woods v. Edwards, 51 F.3d 577, 580 (5th Cir.1995) (“It is settled that prison officials cannot act against a prisoner for availing himself of the courts and attempting to defend his constitutional rights”).
In Burton v. Livingston, 791 F.2d 97 (8th Cir.1986), the complaint alleged threats made by a prison guard in retaliation for testimony given by the inmate in another case. These facts supported a section 1983 claim for violation of the prisoner’s “due-process and First Amendment right of access to the federal courts.” Id. at 100. Accord Newsom v. Norris, 888 F.2d 371, 375 (6th Cir.1989).
denied release on parole based on the exercise of his right of access to the courts alleges an impermissible and unconstitutional reason for the Board’s action. That claim is not based on the abrogation of a liberty interest, and consequently, is not within the ambit of the reasoning underlying the decision in Reider. It is at least arguable, therefore, that Burkett’s claim is not controlled by Reider. However, the application of that case to other instances of constitutional violations shows that the Commonwealth Court has given the holding a broad sweep. Similarly, Burkett’s claim that he was
It is important, therefore, to assess the attitude of the state’s highest court. In discussing the right of appeal in parole cases, the Pennsylvania Supreme Court in Bronson explained that the state’s constitution guarantees the right to an appeal from an administrative agency (including the Pennsylvania Parole Board) to a court. 421 A.2d at 1024-25. Implementing legislation designated the Commonwealth Court as the appropriate court of record for agency review. 42 Pa. Cons.Stat.Ann. § 763. Bronson concluded that the Commonwealth Court had jurisdiction over the appeal from a parole revocation decision made by the Board. 421 A.2d at 1025-26. In its opinion, the state Supreme Court did not indicate in any way that Commonwealth Court would lack jurisdiction if the controversy had centered on denial, rather than revocation, of parole.
reasonable to assume that the Commonwealth Court has jurisdiction over appeals from a denial of parole based on constitutional grounds other than an alleged abrogation of a liberty interest. To that extent, we conclude that Reider does not state the law As we read Bronson, therefore, it is *141in Pennsylvania and that Burkett was entitled to appeal to the Commonwealth Court.4
One other procedural avenue appears open to Burkett. Reider itself acknowledged that “mandamus is available to compel the Board to conduct a hearing or correct a mistake in applying the law.” 514 A.2d at 972 n.4. In Commonwealth ex rel. Saltzburg v. Fulcomer, 382 Pa.Super. 422, 555 A.2d 912 (1989), the Superior Court noted a distinction between an appeal from a “discretionary decision” of the Board and an action that seeks to compel the Board to act in accordance with its own regulations. In the latter circumstance, the Superior Court held that mandamus was the appropriate remedy and transferred an appeal from a Board ruling to the Commonwealth Court. Id. 555 A.2d at 914.
We also consider whether Burkett may be able to proceed in the state courts under the Post Conviction Relief Act or by requesting a writ of habeas corpus. In 1988, Pennsylvania enacted the Post Conviction Relief Act. It provides “the sole means of obtaining collateral relief and encompasses all other common law and statutory remedies for the same purpose ... including habeas corpus and co-ram nobis.” 42 Pa. Cons.Stat. Ann. § 9542.
In Commonwealth v. Hayes, 408 Pa.Super. 68, 596 A.2d 195 (1991), the Superior Court held that the language of the Post Conviction Relief Act precluded resort to the writ of coram nobis. No appellate court in Pennsylvania, to our knowledge, has considered the question of whether-the Act has totally replaced the writ of habeas corpus. We note, however, that the Pennsylvania Constitution art. I, § 14 provides that the writ of habeas corpus may not be suspended unless rebellion or public safety may require it.
The Post Conviction Relief Act, moreover, is limited to persons who assert they were convicted of crimes they did not commit and persons who are serving illegal sentences. 42 Pa.Cons.Stat.Ann. § 9542. Petitioner here does not fall into either of those categories. Instead, he alleges that he is unjustly incarcerated because of an unconstitutional denial of parole. He does not deny commission of the crime, nor in this petition does he contend that the sentence is illegal.
The Pennsylvania Supreme Court has not yet addressed the effect of the Act on habeas corpus, and so we are required to predict what its ruling would be. Because of the state constitutional provisions prohibiting impairment of the right to a writ of habeas corpus, we would expect that in the event that the Commonwealth Court cannot adjudicate this matter, the state’s highest court would permit a habeas corpus action in the circumstances present here. Alternatively, we predict that the state’s highest court would conclude that the petition here is outside the scope of the Post Conviction Relief Act.
In Commonwealth v. Isabell, 503 Pa. 2, 467 A.2d 1287, 1291 (1983) (challenging Bureau of Corrections’ interpretation of term of incarceration), the state Supreme Court held that where a prisoner did not mount a “direct or collateral attack on the conviction or sentence imposed by the trial court,” the proper remedy was not under the Post Conviction Hearing Act (the predecessor statute), and “[consequently, appellant may resort to the writ of habeas corpus ad subjiciendum.” Id. Similarly, in Commonwealth v. Maute, 263 Pa.Super. 220, 397 A.2d 826, 829 (1979), the Superior Court held that “[a] claim for ‘cruel and unusual punishment’ is more properly cognizable in a petition for habeas corpus” than under the Post Conviction Hearing Act.
Those two cases were decided before the Post Conviction Relief Act was enacted, but we believe the reasoning in those opinions is sound and applicable to the current statute. It follows that claims of unconstitutional violations not seeking to set aside a sentence or a conviction are outside the Post Conviction Relief Act.
We read Isabell, 467 A.2d at 1291, as permitting a petition for habeas corpus relief in *142the circumstances here because Burkett is not making a direct or collateral attack on his conviction or sentence. We recognize that in 1944, the Supreme Court of Pennsylvania held that a parole denial could not be challenged by using a petition for habeas corpus to allege that the Board had been neither fair nor impartial. See Commonwealth ex rel. Biglow v. Ashe, 348 Pa. 409, 35 A.2d 340 (1944). There was no charge of unconstitutional action in that case and we need not resolve the conflict (if any) between it and Isabell. Fundamentally, it is the role of the Pennsylvania courts to clarify the law of that state. It is enough for our purposes to note that, should the Commonwealth Court not have jurisdiction, either by appeal or mandamus, relief by habeas corpus has not been foreclosed by holdings of the state Supreme Court.
It appears to us, therefore, that Burkett has available three potential ways of attacking the denial of parole in Pennsylvania courts — appeal, mandamus, or habeas corpus. The somewhat unsettled state law in this area is a factor to consider in deciding whether we should proceed to the merits, rather than requiring Burkett to exhaust state remedies. Obviously, a ruling by the state Supreme Court or Commonwealth Court discussing the scope of the Reider opinion and the proper channels for bringing such claims would be helpful in this frequently litigated area of state law.
Clarification is highly desirable and counsels in favor of exhaustion of state remedies rather than resolution on the merits in the first instance by the district court. Failure to require resort to the state courts in these circumstances would not be consistent with a sound exercise of discretion. Moreover, we find some gaps in the record, such as the absence of the letters written to the Parole Board by the sentencing judge and the district attorney, that make us hesitant to address the merits of Burkett’s petition at this stage.
We emphasize that our holding does not express any view as to the validity of Burk-ett’s claim. We merely recognize that an allegation that parole was denied in retaliation for the successful exercise of the right of access to the courts states a cognizable claim for relief.
Pennsylvania law provides that the Parole Board “shall, in all cases, consider” recommendations from district attorneys and sentencing judges, 61 Pa.Cons.Stat.Ann. § 331.19, while retaining “exclusive power to parole.” 61 Pa.Cons.Stat.Ann. § 331.17. The mere fact that recommendations were submitted to the Board is not enough, in itself, to establish Burkett’s claim. He must show more. The determination of whether there was any retaliation, and whether that retaliation influenced the decision of the Parole Board, is a matter that must be addressed by the state courts.
Accordingly, we will remand this case to the district court with instructions to dismiss the petition so that Burkett may proceed in the state court.
. Although the district court order uses the term exhaustion of "administrative remedies,” it is clear on examination of the record and in context that this was an inadvertent misnomer and that what was intended was "exhaustion of state remedies.”
. Section 106 of the Act provides that a second or successive application for habeas corpus shall be dismissed unless, inter alia, a factual predicate exists that could not have been discovered earlier. In the case at hand, that circumstance exists. Section 106 also provides that a second petition must first be presented to the Court of Appeals before it may be filed in the district court. The present petition had been filed before that amendment to § 2254 was enacted, and consequently, it does not apply here.
. Compare Barnhouse v. Pennsylvania Bd. of Probation and Parole, 89 Pa.Cmwlth. 512, 492 A.2d 1182 (1985); Counts v. Pennsylvania Bd. of Probation and Parole, 87 Pa.Cmwlth. 277, 487 A.2d 450 (1985); Kastner v. Pennsylvania Bd. of Probation and Parole, 78 Pa.Cmwlth. 157, 467 A.2d 89 (1983); Banks v. Board of Probation and Parole, 4 Pa.Cmwlth. 197, 1971 WL 13031 (1971) (in banc) (review permitted); with LaCamera v. Pennsylvania Bd. of Probation and Parole, 13 Pa.Cmwlth. 85, 317 A.2d 925 (1974) (no judicial review).
. Whether the Parole Board would be estopped from pleading a time bar because of its erroneous representation to Burkett about appealability, we leave to the Commonwealth Court.