A search for the decay of neutral, weakly interacting, long-lived particles using data collected by the ATLAS detector at the LHC is presented. The analysis in this paper uses 36.1 fb$\mathrm{<mrow\; data-mjx-texclass="ORD">-1</mrow>}$ of proton-proton collision data at $s=13$ TeV recorded in 2015-2016. The search employs techniques for reconstructing vertices of long-lived particles decaying into jets in the muon spectrometer exploiting a two vertex strategy and a novel technique that requires only one vertex in association with additional activity in the detector that improves the sensitivity for longer lifetimes. The observed numbers of events are consistent with the expected background and limits for several benchmark signals are determined.