Keyword bids determined from sparse data are described. Initially, a portfolio optimization platform identifies which keywords included in a portfolio of keywords are low-impression keywords. This platform trains a machine learning model to generate bids for the low-impression keywords with historical data from a search engine. In particular, the platform trains this machine learning model according to an algorithm suited for training with sparse amounts of data, e.g., a temporal difference learning algorithm. In contrast, the platform uses different models, trained according to different algorithms than the low-impression keyword model, to generate bids for keywords determined not to be low-impression keywords. Once the low-impression keyword model is trained offline, the platform deploys the model for use online to generate actual bids for the low-impression keywords and submits them to the search engine. The platform continues to update the low-impression keyword model while deployed according to the sparse-data algorithm.