Goal-setting is commonly used in behavior change applications for physical activity. However, for goals to be effective, they need to be tailored to a user’s situation (e.g., motivation, progress). One way to obtain such goals is a collaborative process in which a healthcare professional and client set a goal together, thus making use of the professional’s expertise and the client’s knowledge about their own situation. As healthcare professionals are not always available, we created a dialog with the virtual coach Steph to collaboratively set daily step goals. Since judgments in human decision-making processes are adjusted based on the starting point or anchor, the first step goal proposal Steph makes is likely to influence the user’s final goal and self-efficacy. Situational factors impacting physical activity (e.g., motivation, self-efficacy, available time) or how users process information (e.g., mood) may determine which initial proposals are most effective in getting users to reach their underlying previous activity-based recommended step goals. Using data from 117 people interacting with Steph for up to five days, we designed a reinforcement learning algorithm that considers users’ current and future situations when choosing an initial step goal proposal. Our simulations show that initial step goal proposals matter: choosing optimal ones based on this algorithm could make it more likely that people move to a situation with high motivation, high self-efficacy, and a favorable daily context. Then, they are more likely to achieve, but also to overachieve, their underlying recommended step goals. Our dataset is publicly available.