Methods, systems, and apparatus, including computer programs encoded on computer storage media, for implementing a machine-learned object tracking policy. One of the methods includes receiving a current video frame by a user device having a plurality of installed object trackers, wherein each object tracker is configured to perform a different object tracking procedure on the current video frame rent video frame. The current video frame and one or more object tracks previously generated by the one or more object trackers are provided as input to a trained policy engine that implements a reinforcement learning model to generate a particular object tracking plan. A particular object tracking plan is selected based on the output of the reinforcement learning model, and the selected object tracking plan is performed on the current video frame to generate one or more updated object tracks for the current video frame.