This is an appeal from a judgment of the United States District Court for the Southern District of New York, Griesa, J., dismissing the plaintiffs’ breach of contract class action against defendant insurance carrier for failure to exhaust administrative remedies, 796 F.Supp. 764.
This action was brought by subscribers to several major medical insurance plans issued by defendant Empire Blue Cross and Blue Shield (Empire), challenging Empire’s January 1, 1990 reformulation of the geographic zones used in determining physician reimbursement amounts. On that date, Empire abandoned its use of three broad geographic pricing zones in favor of smaller “zip code cluster pricing” zones. Plaintiff class consists of all Empire subscribers who submitted claims on or after January 1, 1990 and on whose behalf reduced payments of benefits were made because of the shift to zip code zone pricing. Plaintiffs alleged that Empire breached its contracts by changing its method of determining reimbursement amounts unilaterally and without subscriber consent, thereby reducing reimbursements to the plaintiffs. *590Plaintiffs also alleged that by improperly implementing this change, Empire reduced its level of reimbursements to subscribers overall.
Empire moved the district court to dismiss the complaint pursuant to Fed. R.Civ.P. 12(b)(6) for failure to state a claim upon which relief can be granted, on grounds, inter alia, that plaintiffs had failed to exhaust their administrative remedies prior to bringing the action. Because materials in addition to the complaint were submitted on the exhaustion issue, the district court converted the motion to a Fed. R.Civ.P. 56 motion for summary judgment pursuant to Fed.R.Civ.P. 12(b). The district court granted the motion, holding that the named plaintiff who was a federal employee had failed to make a required appeal to the Office of Personnel Management (OPM) and that the non-government employee named plaintiffs had failed to make a required appeal to Empire. We agree with the district court and affirm the judgment.
BACKGROUND
The complaint alleges that at the time this action arose, named plaintiff Anne Kennedy was a federal employee, a resident of Bronx County, New York, and an Empire major medical insurance subscriber under the “Federal Employee Program.” Named plaintiff Michael Chubre, a resident of King’s County, New York, represents the estate of Emily Chubre, who was an Empire subscriber under the “Wraparound” group plan. Named plaintiffs Jo-sette Boehm and Ralph Russo were residents of Nassau and Queens Counties, New York, respectively, and Empire subscribers under the “TraditionPLUS” group plan. The class of plaintiffs consists of two subclasses: (1) federal employees, whose claims are governed by the Federal Employees Health Benefits Act, 5 U.S.C. § 8901 et seq. (FEHBA), and (2) non-federal employees, whose claims are governed by the Employee Retirement Income Security Act of 1974, 29 U.S.C. § 1001 et seq. (ERISA).
Federal employee plaintiffs (FEHBA plaintiffs) such as Kennedy obtain their health benefits through the Federal Employees Health Benefits Program (FEHBP) which is governed by the provisions of FEHBA. Under FEHBA, OPM has the authority to contract with insurance carriers to provide benefits to participants in FEHBP. 5 U.S.C. § 8902(a). Insurance carriers which seek to participate in FEHBP must be approved by and enter into a contract with OPM. 5 U.S.C. § 8902. FEHBA provides that, as a condition to participating in FEHBP, insurance carriers must agree to be bound by OPM’s interpretation of their contracts in disputes over individual claims. 5 U.S.C. § 8902(j).
Plaintiffs who are not federal employees (ERISA plaintiffs), such as the remaining three named plaintiffs, obtained their health insurance coverage through their employers, choosing one of Empire’s policies such as Wraparound or Tradition-PLUS. Typically in such cases, the employer contracts with Empire to provide coverage for its employees. Claims under such employer benefit plans are governed by the provisions of ERISA.
All of the plans to which members of the plaintiff class subscribed reimburse major medical expenses based on schedules of “Customary Charges.” The contracts define Customary Charge to be the amount charged by most providers with training and experience similar to the covered person’s provider who render the same type of service in the same area where the service was provided. Empire sets the Schedule of Customary Charges for a particular area by reviewing all claims submitted to them for the same procedure in the same area during a particular period of time, and then establishing the Customary Charges at a level sufficient to pay the cost of the service by ninety percent of the providers in that area.
Prior to January 1, 1990, Empire divided its operating area into three geographic zones for purposes of calculating Customary Charges. On January 1, 1990, Empire implemented its “zip code cluster pricing,” dividing its operating area into a larger number of zones defined by clusters of United States Postal Service zip codes. Empire states that the change was in re*591sponse to provider requests that Empire use Customary Charges that are more geographically specific. Empire made this change without the consent of policyholders, believing that such an adjustment fell within its discretion to define relevant “geographic areas” under the contracts.
Plaintiff Kennedy is the only named plaintiff to have appealed to Empire about the reductions in benefits at issue here. Upon receiving notification from Empire of the amount covered for anesthesia services rendered to Kennedy (an amount less than that received on a similar claim submitted before January 1, 1990), Dr. Joel Archer, on behalf of Kennedy, requested by letter dated May 18, 1990, that Empire review its determination. Empire reviewed the claim, concluded that the amount paid was correct and informed Dr. Archer by telephone of its determination and of Dr. Archer’s right to appeal to OPM. By letter dated June 11, 1990, Dr. Archer asked Empire for a written rationale for its determination. By letter dated June 15, 1990, Yvonne S. Archer, Executive Director of the New York State Federation of Anesthesiologists, Inc. (Federation), again asked for a written rationale and stated to Empire that “[u]nder the Federal Employee Program, contract carriers (not government’s Office of Personnel Management) have responsibility for implementing usual and customary fee screens. Your suggestion that the doctor now apply to Washington for an appeal is inappropriate.” Empire sent a written response dated June 29,1990 to Dr. Archer, detailing its calculations and again informing him of his right to appeal to OPM.
On July 14, 1990, Yvonne Archer wrote directly to the president of Empire, repeating her assertion that Empire's calculations were inaccurate and that appeal to OPM would be pointless. On July 31, 1990, Empire responded by letter, explaining for the first time the January 1, 1990 switch to zip code zone pricing. Yvonne Archer wrote back to Empire on August 13, 1990, stating that despite Empire’s methodology, “when an established method of computation is substituted for one that reduces prevail-ings by about Vz, it is reasonable to assume that the new combined statistics are faulty all around,” and asking to be provided with the pricing schedules for Manhattan and the zip code clusters used in calculating the schedules. A follow-up letter was sent by the Federation’s attorney, Whitney North Seymour, Jr., on October 26, 1990. On December 27, 1990, Empire wrote to Seymour, informing him that the requested pricing and zone information is “proprietary and confidential information and will not be released outside the Corporation.” No appeal was ever made to OPM by anyone representing Kennedy.
Plaintiffs filed their complaint in New York state court on November 18, 1991, alleging a one count state law breach of contract claim. Empire timely removed the case to the United States District Court based on federal question jurisdiction, given that ERISA preempts state law contract claims respecting denials of benefits under employee benefit plans. Pilot Life Ins. Co. v. Dedeaux, 481 U.S. 41, 107 S.Ct. 1549, 95 L.Ed.2d 39 (1987). On January 9, 1992, Empire moved to dismiss the complaint pursuant to Fed.R.Civ.P. 12(b)(6) for failure to state a claim upon which relief can be granted on grounds that (1) the language of the contracts and the relevant law make clear that Empire’s adoption of zip code zones did not violate any contractual or statutory right of any of its subscribers, and (2) the plaintiffs have failed to allege and pursue the exhaustion of their administrative remedies. To demonstrate exhaustion of administrative remedies, plaintiffs included with their opposition papers the May 18, 1990 letter of Dr. Archer, the October 26, 1990 letter of Seymour and the December 27, 1990 letter of Empire.
■ Because materials outside of the complaint were introduced on the exhaustion issue, the district court, pursuant to Fed. R.Civ.P. 12(b), converted the motion to dismiss into a Fed.R.Civ.P. 56 motion for summary judgment and dismissed the complaint. The complaint was dismissed for failure to exhaust administrative remedies on grounds that the FEHBA plaintiff, Kennedy, had failed to seek OPM review prior to filing the action and that the ERISA plaintiffs failed to seek review even from *592Empire. Plaintiffs timely filed a notice of appeal.
DISCUSSION
Plaintiffs appeal the judgment of the district court on the grounds that (1) the district court improperly converted the Rule 12(b)(6) motion into a Rule 56 motion, (2) the district court erroneously held that exhaustion of OPM review is required of the FEHBA plaintiffs, and (3) the district court erroneously held that the ERISA and FEH-BA plaintiffs had failed to make a sufficient showing that exhaustion would be futile. We reject each of these grounds and affirm the judgment of the district court.
A. Conversion to Summary Judgment
Plaintiffs claim that the Rule 12(b)(6) motion was improperly converted into a Rule 56 motion because it was done sua sponte by the district court without notice to the parties or the opportunity for plaintiffs to provide full documentary proof of exhaustion. Rule 12(b) of the Fed. R.Civ.P. provides that:
If, on a motion asserting the defense numbered (6) to dismiss for failure of the pleading to state a elaim upon which relief can be granted, matters outside the pleading are presented to and not excluded by the court, the motion shall be treated as one for summary judgment and disposed of as provided in Rule 56, and all parties shall be given reasonable opportunity to present all material made pertinent to such a motion by Rule 56.
We find no error in the district court’s conversion of the motion. In In re G. & A. Books, 770 F.2d 288 (2d Cir.1985), cert. denied, 475 U.S. 1015, 106 S.Ct. 1195, 89 L.Ed.2d 310 (1986), we articulated the standard for determining the adequacy of notice of conversion of a motion to dismiss into a motion for summary judgment: “The essential inquiry is whether the appellant should reasonably have recognized the possibility that the motion might be converted into one for summary judgment or was taken by surprise and deprived of a reasonable opportunity to meet facts outside the pleadings.” Id. at 295. Plaintiffs were on clear notice from Empire’s motion papers that dismissal was being sought on grounds of lack of exhaustion of administrative remedies. To demonstrate exhaustion, plaintiffs supplemented their opposition papers with three letters exchanged between Empire and representatives of Kennedy. Additionally, the only documentation plaintiffs sought to add to the record was more examples of such correspondence, none of which would provide proof to refute the district court’s finding that ERISA plaintiffs made no appeal to Empire and FEHBA plaintiffs made no appeal to OPM. Plaintiffs were not “taken by surprise and deprived of a reasonable opportunity to meet facts outside the pleadings.” Id.
B. Requirement of Exhaustion of OPM Review
The district court, citing the Eleventh Circuit case of Kobleur v. Group Hospitalization & Medical Servs., 954 F.2d 705 (11th Cir.), reh’g denied, 963 F.2d 387 (11th Cir.1992), held that holders of health insurance policies governed by FEHBA must appeal disputed claims to OPM before seeking judicial review. Because named plaintiff Kennedy did not seek OPM review of her disputed claim or make a clear and positive showing of the futility of such an appeal, the district court dismissed the complaint as to the FEHBA plaintiffs.
The doctrine of exhaustion of administrative remedies provides “that no one is entitled to judicial relief for a supposed or threatened injury until the prescribed administrative remedy has been exhausted.” Myers v. Bethlehem Shipbuilding Corp., 303 U.S. 41, 50-51, 58 S.Ct. 459, 463, 82 L.Ed. 638 (1938). The exhaustion requirement may arise from explicit statutory language or from an administrative scheme providing for agency relief. See Kobleur, 954 F.2d at 709.
There is currently a split of authority with respect to the exhaustion requirements for plans governed by FEHBA. FEHBA contains no specific statutory language requiring exhaustion of administrative remedies. However, the split arises from the ambiguous use of the word *593“may” in the relevant regulation, promulgated pursuant to a provision of FEHBA, 5 U.S.C. § 8913:
Each health benefits plan adjudicates claims filed under the plan. An enrollee must initially submit all claims to the health benefits plan in which he or she is enrolled. If the plan denies a claim, the enrollee may ask the plan to reconsider the denial. If the plan affirms its denial or fails to respond as required by paragraph (b) of this section, the enrollee may ask OPM to review the claim.
5 C.F.R. § 890.105(a) (1992) (emphasis added).
In Skoller v. Blue Cross-Blue Shield of Greater New York, 584 F.Supp. 288 (S.D.N.Y.1984), the court interpreted the word “may” to mean that OPM review was allowed but not required before a claimant could resort to the courts to resolve a disputed claim. “[Njeither Congress nor OPM has manifested any intent to make OPM review either an exclusive remedy or a mandatory prerequisite to judicial resolution of disputes over contract interpretation.” Id. at 291; see also Eidler v. Blue Cross Blue Shield United of Wisconsin, 671 F.Supp. 1213, 1216 (E.D.Wis.1987) (“It would seem strange that Congress would intend foreclosure of judicial review with such permissive language.”). In contrast, in Bateman v. Blue Cross-Blue Shield of Alabama, 579 F.Supp. 265 (M.D.Ala.1984), the court interpreted “may” to mean that OPM review is required before seeking judicial relief. “The word in its context means just what it says: the claimant may seek OPM review, or not seek review and accept the carrier’s decision; the choice is the claimant’s.” Id. at 268.
In 1986, in response to a suggestion that it permit direct judicial review in lieu of administrative procedures, OPM explained its official position on 5 C.F.R. § 890.105:
In the employee benefits area, OPM has traditionally argued for dismissal of court cases when the individual has failed to exhaust administrative remedies. The purpose of OPM’s disputed claims review procedures is to assist en-rollees in avoiding the costs and time delays associated with legal proceedings. Consequently, we do not favor a regulation calling for review by the courts before all administrative remedies have been exhausted.
51 Fed.Reg. 18,562 (1986). The only United States Court of Appeals to interpret section 890.105 in light of this official OPM position is the Eleventh Circuit. In Kobleur, the court held that section 890.105 requires OPM review before an action may be brought against an insurance carrier. Kobleur, 954 F.2d at 711. The court relied on Martin v. Occupational Safety and Health Review Comm’n, — U.S. -, -, 111 S.Ct. 1171, 1176, 113 L.Ed.2d 117 (1991), which held that a court must give effect to an agency’s interpretation of its own regulation as long as the interpretation is reasonable. We agree with the Eleventh Circuit’s reasoning in Kobleur:
Congress gave OPM the authority to administer the federal benefits program, to proscribe [sic] regulations necessary to meet this end, and to bind carriers to OPM’s interpretations of their plans. The delegation of such authority, combined with the absence of any language in the FEHBA precluding the possibility of an exhaustion requirement, convinces us of Congress’ faith in OPM’s ability to protect federal employees through its administration of the program.
954 F.2d at 711.
Plaintiffs argue that giving effect to OPM’s interpretation of section 890.105 is improper because it conflicts with the plain will of Congress. See Iglesias v. United States, 848 F.2d 362, 366 (2d Cir.1988) (“A regulation, however, may not serve to amend a statute, or to add to the statute something which is not there.” (citations omitted)). Plaintiffs argue that
[t]he critical point is that OPM’s interpretation is at odds with Congressional intent to protect and benefit beneficiaries. The agency statement changes OPM review from a shield for the beneficiary to a sword for the carrier. This renders the mandatory exhaustion requirement espoused by OPM invalid. The OPM review must remain optional for the insured employee, to use or not as serves his or her best interests.
*594We reject this reasoning and instead agree with the Kobleur Court. Congress gave OPM substantial administrative authority over the FEHBP, including not only the right to interpret the carrier’s contract, but also the right to bind the carrier to its interpretation of the contract. 5 U.S.C. § 8902(j).1 Congress clearly intended this to be an added protection against improper conduct by a carrier, without forcing subscribers to resort to costly and time consuming litigation. Were OPM review optional, the usefulness of this right of OPM to bind carriers would be diminished as a tool for carrying out Congress’ intent to protect and benefit FEHBP participants and their beneficiaries.
C. Failure to Demonstrate Futility
This Court has recognized “the firmly established federal policy favoring exhaustion of administrative remedies in ERISA cases.” Alfarone v. Bernie Wolff Construction, 788 F.2d 76, 79 (2d Cir.), cert. denied, 479 U.S. 915, 107 S.Ct. 316, 93 L.Ed.2d 289 (1986). ERISA does not provide for OPM review, but instead requires that all benefit plans provide for carrier review. 29 U.S.C. § 1133.2 Thus, exhaustion in the context of ERISA requires only those administrative appeals provided for in the relevant plan or policy. See Amato v. Bernard, 618 F.2d 559, 567 (9th Cir.1980) (requirement that plan provide remedies suggests Congress’ intent to have courts require exhaustion of these remedies); Leonelli v. Pennwalt Corp., 887 F.2d 1195, 1199 (2d Cir.1989) (noting requirement that ERISA claimants exhaust administrative remedies provided for by their plan).
Plaintiffs argue that although the ERISA plaintiffs did not appeal their benefit reductions to Empire, the correspondence between Kennedy’s representatives and Empire demonstrates the futility of any such appeal, thus the district court erred in dismissing the complaint as to the ERISA plaintiffs on grounds of failure to exhaust administrative remedies. We reject this reasoning.
To understand the futility exception to the exhaustion requirement, the purposes behind the requirement of exhaustion in ERISA cases should be understood. In Denton v. First Nat’l Bank of Waco, Texas, 765 F.2d 1295 (5th Cir.), reh’g denied, 772 F.2d 904 (5th Cir.1985), the Fifth Circuit explained:
The primary purposes of the exhaustion requirement are to: (1) uphold Congress’ desire that ERISA trustees be responsible for their actions, not the federal courts; (2) provide a sufficiently clear record of administrative action if litigation should ensue; and (3) assure that any judicial review of fiduciary action (or inaction) is made under the arbitrary and capricious standard, not de novo.
Id. at 1300. The Amato Court reasoned that the requirement was intended to “help reduce the number of frivolous lawsuits under ERISA; to promote the consistent treatment of claims for benefits; to provide a nonadversarial method of claims settlement; and to minimize the costs of claims settlement for all concerned.” 618 F.2d at 567. Where claimants make a “clear and positive showing” that pursuing available administrative remedies would be futile, the purposes behind the requirement of exhaustion are no longer served, and thus a court will release the claimant from the requirement. Fizer v. Safeway Stores, 586 F.2d 182, 183 (10th Cir.1978) (quoting Imel v. Zohn Mfg. Co., 481 F.2d 181, 184 (10th *595Cir.1973), cert. denied, 415 U.S. 915, 94 S.Ct. 1411, 39 L.Ed.2d 469 (1974)).
There is no evidence in the record that any ERISA plaintiff even notified Empire of any disputed claim. Instead, plaintiffs contend that the FEHBA plaintiff correspondence adequately demonstrates futility as to the ERISA plaintiffs, because the disputed zip code zone policy is universal to all plans at issue. We do not agree that the ERISA plaintiffs can claim exhaustion based on the FEHBA plaintiff correspondence.
While the zip code zone policy may apply to both the FEHBA and ERISA plaintiffs, there are substantial differences between the two subclasses of plaintiffs which make any claim of exhaustion by one subclass based on the appeals of the other inappropriate. The FEHBA and ERISA plaintiffs subscribe to different plans (Federal Employee Program for FEHBA plaintiffs and Wraparound and TraditionPLUS for ERISA plaintiffs), each of which is differently worded with respect to Empire’s ability to unilaterally make administrative changes such as changes to its benefit calculation methods.3 Additionally, as to the FEHBA plaintiffs, Empire has contracted with OPM and as to the ERISA plaintiffs, Empire has contracted with the individual employers. Empire may well have a policy of treating claim disputes from each subclass differently, knowing that FEHBA plaintiffs have an additional avenue of appeal open to them. We hold that the ERISA plaintiffs have not made a “clear and positive showing” of futility, given that they took no action whatsoever with respect to their disputed claims before bringing this action and that they are not under the same contract as the FEHBA plaintiffs.
Plaintiffs finally claim that any appeal to OPM by the FEHBA plaintiffs would have been futile because a dispute over the setting of Customary Charges “is beyond the competence of OPM, which plays no part in the development of ‘customary charge’ rates.” To the contrary, OPM has authority pursuant to 5 U.S.C. § 8902(j) to interpret disputed health plan provisions in individual cases, although it may not unilaterally alter or amend plan terms. Hayes v. Prudential Ins. Co. of America, 819 F.2d 921, 924 (9th Cir.1987), cert. denied, 484 U.S. 1060, 108 S.Ct. 1014, 98 L.Ed.2d 980 (1988). This authority would allow it to interpret the provisions concerning Customary Charges in resolving the FEHBA plaintiffs’ disputes over such charges. We find the futility exception to the exhaustion requirement inapplicable to the FEHBA plaintiffs.
*596CONCLUSION
For the foregoing reasons we affirm the judgment of the district court dismissing plaintiff class’ complaint on grounds of failure to exhaust administrative remedies.
. 5 U.S.C. § 8902(j) states:
Each contract under this chapter shall require the carrier to agree to pay for or provide a health service or supply in an individual case if the Office finds that the employee, annuitant, family member, former spouse, or person having continued coverage under section 8905a of this title is entitled thereto under the terms of the contract.
. 29 U.S.C. § 1133 provides:
In accordance with regulations of the Secretary, every employee benefit plan shall—(1) provide adequate notice in writing to any participant or beneficiary whose claim for benefits under the plan has been denied, setting forth the specific reasons for such denial, written in a manner calculated to be understood by the participant, and (2) afford a reasonable opportunity to any participant whose claim for benefits has been denied for a full and fair review by the appropriate named fiduciary of the decision denying the claim.
. Illustrative of the differences in contract language are the following contract excerpts relating to changes in Customary Charges.
The FEHBP contract provides, in pertinent part:
(b) Physician Benefit Payments and Conditions.
(1) Usual, Customary and Reasonable Charges.
(A) Except as otherwise noted in this Article, the Plan which pays the benefits shall determine, with respect to the amount of any benefit payment, "usual,” "customary,” and “reasonable” charges as those terms are defined in the Brochure (RI 71-5). Both parties recognize that flexibility in methods and procedures employed by Participating Plans in determining “usual," and "customary,” and "reasonable” charges is required.
(B)' ... Plans also shall maintain records of physicians’ "customary” charges. Such records may be maintained by geographic area(s), medical specialty and other factors, if any, as deemed appropriate by the Plans. Plans shall periodically review their records of "usual,” and "customary” charges in accordance with local Plan practice.
The TraditionPLUS contract provides:
b. Reimbursement For Benefits For Services Of Other Providers
The Schedule of Customary Charges is updated periodically based upon a review of submitted claims in the preceding review period.
G. Right To Develop Guidelines And Administrative Rules
We may develop or adopt standards which describe in more detail when we will or will not make payments under this Contract and administrative rules pertaining to enrollment and other administrative matters.
Empire shall have all the powers necessary or appropriate to enable it to carry out its duties in connection with the administration of this Contract, including, without limitation thereto, the power to construe this Contract, to determine all questions arising under this Contract, and to make and establish (and thereafter change) rules and regulations and procedures with respect to this Contract.