The knowledge of link packet loss rates (PLRs) at different PHY layer configurations is vital for a number of wireless network optimization schemes. However, the very large number of PHY layer configurations offered by modern 802.11 n/ac networks has made probing-based PLR estimation at each available configuration extremely challenging. In this paper, we seek to answer the question “How to estimate the PLRs at each available PHY layer configuration with minimal overhead?” Our analysis of the PLR datasets collected from three 802.11 n/ac testbeds reveals that, for any given link, there are several configurations with similar PLR. However, capturing this similarity using well-known link quality indicators like RSSI, or PHY layer features such as MCS or number of MIMO streams is hard. Consequently, we explore the approach of clustering the available PHY layer configurations into a small number of clusters with similar PLR, independent of any other parameter, and only probe one representative configuration in each cluster. Using two real-world case studies — rate adaptation and multihop routing, we show that the proposed clustering-based PLR estimation helps network optimization schemes to reach optimal configurations faster leading to significant performance improvements.