Automated collision avoidance is a central topic in multi-agent systems that consist of mobile agents. One simple approach to pursue system-wide performance is a centralized algorithm, which, however, becomes computationally expensive when involving a large number of agents. There have thus been proposed fully distributed collision avoidance algorithms that can naturally handle many-to-many encounter situations. The DSSA⁺ is one of those algorithms, which is heuristic and incomplete but has lower communication and computation overheads than other counterparts. However, the DSSA⁺ and some other distributed collision avoidance algorithms basically optimize the agents’ behavior only in the short term, not caring about the total efficiency in their paths. This may result in some agents’ paths with over-deviation or over-stagnation. In this paper, we present Distributed Stochastic Search algorithm with a deep Q-network (DSSQ), in which the agents can generate time-efficient collision-free paths while they learn independently whether to detour or change speeds by Deep Reinforcement Learning. A key idea in the learning principle of the DSSQ is to let the agents pursue their individual optimality. We have experimentally confirmed that a sequence of short-term system-optimal solutions found by the DSSA⁺ gradually becomes long-term individually optimal for every agent.