Abstract: Program execution speed critically depends on reducing cache misses, as cache misses are orders of magnitude slower than hits. To reduce cache misses, we focus on the problem of cache replacement: choosing which cache line to evict upon inserting a new line. This is challenging because it requires planning far ahead and currently there is no known practical solution. As a result, current replacement policies typically resort to heuristics designed for specific common access patterns, which fail on more diverse and complex access patterns. In contrast, we propose an imitation learning approach to automatically learn cache access patterns by leveraging Belady’s, an oracle policy that computes the optimal eviction decision given the future cache accesses. While directly applying Belady's is infeasible since the future is unknown, we train a policy conditioned only on past accesses that accurately approximates Belady's even on diverse and complex access patterns. When evaluated on four of the most memory-intensive SPEC applications, our learned policy reduces cache miss rates by 15% over the current state of the art. In addition, on a large-scale web search benchmark, our learned policy reduces cache miss rates by 66% over a conventional LRU policy. We release a Gym environment to facilitate research in this area, as data is plentiful, and further advancements can have significant real-world impact.