This paper studies optimal mechanisms in a dynamic principal-agent setting with costly monitoring. The agent's private effort affects transitions in ``quality'' which evolves stochastically over time according to a Markov chain. The principal schedules inspections and makes payments based on  inspection outcomes and the agent's unverifiable reports. I derive optimal monitoring policies with deterministic and randomized inspection schedules. When the agent is perfectly informed about quality, mechanisms with random inspections achieve approximately first-best. In contrast, deterministic inspections can be optimal when the agent is imperfectly informed about quality. When using deterministic inspections, the principal faces a trade off between paying the agent for revealing low quality and lowering the cost of monitoring.