Implementations are directed to using an assistant to initiate automated telephone calls with entities. Some implementations identify an item of interest, identify a group of entities associated with the item, and initiate the calls with the entities. During a given call with a given entity, the assistant can request a status update regarding the item, and determine a temporal delay before initiating another call with the given entity to request a further status update regarding the item based on information received responsive to the request. Other implementations receive a request to perform an action on behalf of a user, identify a group of entities that can perform the action, and initiate a given call with a given entity. During the given call, the assistant can initiate an additional call with an additional entity, and generate notification(s), for the user, based on result(s) of the given call and/or the additional call.