Adaptive read-threshold schemes for a memory system determine read-threshold with the lowest BER/UECC failure-rates while continuing to serve the host-reads with the required QoS. When it is determined that the QoS or other quality metric is not met for a particular read-threshold, which may be an initial, default, read-threshold, the performance of other read-thresholds are estimated. These estimates may then be used to determine an optimal read-threshold. During the iterative process, selection variables, e.g., how many times, and for which read commands, to use each of the non-default read-thresholds in future read-attempts may be determined on-the-fly.