With rapid growth in unhealthy diet behaviors, implementing strategies that improve healthy eating is becoming increasingly important. One approach to improve diet behavior is to continuously monitor dietary intake (e.g., calorie intake) and provide educational, motivational, and dietary recommendation feedback. Although technologies based on wearable sensors, mobile applications, and light-weight cameras exist to gather diet-related information such as food type and eating time, there remains a gap in research on how to use such information to close the loop and provide feedback to the user to improve healthy diet. We address this knowledge gap by introducing a diet behavior change framework that generates real-time diet recommendations based on a user’s food intake and considering user’s deviation from the suggested diet routine. We formulate the problem of optimal diet recommendation as a sequential decision making problem and design a greedy algorithm that provides diet recommendations such that the amount of change in user’s dietary habits is minimized while ensuring that the user’s diet goal is achieved within a given time-frame. This novel approach is inspired by the Social Cognitive Theory, which emphasizes behavioral monitoring and small incremental goals as being important to behavior change. Our optimization algorithm integrates data from a user’s past dietary intake as well as the USDA nutrition dataset to identify optimal diet changes. We demonstrate the feasibility of our optimization algorithms for diet behavior change using real-data collected in two study cohorts with a combined N=10 healthy participants who recorded their diet for up to 21 days.