Millions of Americans undergo colonoscopy screening for colorectal cancer (CRC) prevention and surveillance every year. The efficiency of colonoscopy operations depends on how often patients are screened, which is a complex and controversial decision, as reflected by the discrepancy between clinical practice and guidelines. We develop a partially observable Markov decision process to optimize colonoscopy screening policies for the objective of maximizing total quality-adjusted life years. Our model incorporates age, gender, and risk of having CRC into the screening decisions and therefore provides a novel framework for personalized CRC screening. In addition to deriving the maximum attainable benefit from colonoscopy screening, which reflects the opportunity cost of following current guidelines, our results have several policy implications. Using clinical data, we show that the optimal colonoscopy screening policies may be more aggressive than the guidelines under some conditions. Optimal screening policies recommend that females with CRC history undergo colonoscopy more frequently than males. In contrast, females without CRC history should be screened less frequently than males. This result, which was not recognized before, signifies the role of gender in optimal CRC screening decisions.