Despite the revolutionary impact of immune checkpoint inhibition (ICI) on cancer therapy, for most indications the majority of patients do not sustain a durable clinical benefit. In this work, we explore the theoretical consequences of the existence of multiple states of immune cell exhaustion on response to ICI therapy. In particular, we consider the emerging understanding that T cells can exist in various states: fully functioning cytotoxic cells, reversibly exhausted cells that are minimally cytotoxic but targetable by ICIs, and terminally exhausted cells that are cytotoxic yet not targetable by ICIs. Under the assumption that tumor-induced inflammation triggers the transition between these T cell phenotypes, we developed a conceptual mathematical model of tumor progression subject to treatment with an ICI that accounts for multi-stage immune cell exhaustion. Simulations of a ‘baseline patient’ without intrinsic resistance to ICI reveal that treatment response (complete responder versus non-responder with non-genetic resistance) sensitively depends on both the dose and frequency of drug administration. A virtual population analysis uncovered that while the standard high-dose, low-frequency protocol is indeed an effective strategy for our baseline patient, it fails a significant fraction of the population. Conversely, a metronomic-like strategy that distributes a fixed amount of drug over many doses given close together is predicted to be effective across the largest proportion of the virtual population. Taken together, our theoretical analyses demonstrate the potential of mitigating resistance to checkpoint inhibitors via dose modulation, and also suggest avenues for selecting combination drug partners.