Human-robot collaboration often necessitates the robot to adapt to the uncertainty of human objectives and their induced behaviors. This may require the robot to have a human model to anticipate human partners’ objectives and predict their actions, which is typically learned by the robot through available human data. However, in complex collaboration tasks, a chicken-and-egg problem arises because human data cannot be collected without a collaborative robot policy in the first place. In this article, we describe the human-robot collaboration task with Markov decision models and solve the chicken-and-egg problem by proposing an online robot planning algorithm. This online framework can automatically derive a human model without real human data and plan robust robot actions to support human partners with respect to their uncertain objectives and behaviors. Through experiments with a human-robot co-working scenario, we demonstrate that our online method outperforms the previous offline approach in terms of scalability and the ability to plan robot actions within a bounded time.