Foraging animals make decisions based on cues that are unreliable predictors of reward. In these situations, the ratio with which an animal divides its choices between cues matches the ratios with which they provide reward. This operant matching strategy is widespread amongst vertebrates. Performing operant matching requires animals to possess a valuation of available cues, and to update them when cue-reward relationships change. While neurons that represent value information have been found in several brain regions, less is known about how value is updated. Theoretical studies suggest that the underlying learning rule should contain information regarding reward expectation. However, deciphering these rules in the brain has remained a challenge. To address this, we turned to the mushroom body (MB) of D. melanogaster. Previous work has assigned this region a key role in learning and identified the underlying synaptic mechanisms. The circuit’s connectome is mapped, and it has a well-studied role in behavioral control. This makes it a promising system to understand the learning rule underlying matching behavior. We designed a dynamic foraging task, and showed for the first time, that flies perform operant matching. Our analyses of behavior in this task suggest that flies rely on reward history over multiple trials when making choices. Further, we developed a model that uses the known architecture of the MB to predict behavior. Consistent with the theoretical predictions, but counter to prior expectations, when this model used a learning rule involving reward expectation, it was able to better fit behavior. To establish how this reward expectation is represented in the MB, we have begun imaging experiments in key candidate neurons. Our findings suggest that a learning rule incorporating reward expectation may be a widespread feature of neural circuits and play an essential role in foraging across disparate species.