With rapid growth in unhealthy diet behavior, implementing strategies that improve healthy eating is becoming increasingly important. One approach to improve diet behavior is to monitor dietary intake (e.g., calorie intake) and continuously provide educational, motivational, and 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 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 habit 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 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.