Understand why the query plan was changed
Statistics are one input to the query optimizer but not the only one.  As mentioned in the post, the optimizer also sniffs parameter values during compilation and uses those to generate estimates of the number of rows that will come out of various operations such as filters, joins, and group by using the statistics that exist at the time of compilation.  Furthermore, the storage engine provides row counts for each compilation and this can also change without stats changing (though if you change enough rows, the optimizer eventually forces stats to be recomputed).  Any of these things changing could be the cause of the plan changing from one compilation to the next.  The query store actually also tracks other factors that it internally uses to represent to you whether the query is the same or different semantically through a table called sys.context_settings.  So, ansi null on/off would be one such semantic change that could also cause differences in results.  The query store abstracts these from you, but if you were to, for example, create a loop in a stored procedure that changed ansi nulls on/off and then run the same statement over and over in the loop, you'd actually get that to compile over and over (each time the settings are changed from the last time the statement in that part of the sproc is compiled) and this would also give you a chance to have new parameters sniffed on each execution.  These would technically show up as different queries in the query store but to the SQL engine these are holding the same statement slot in the cached query plan for the stored procedure.

SQL 2017+ contains a feature called Automatic Tuning which can auto-force the old plan for you for large regressions.  Azure SQL DB also has this same feature.  In the future, we hope to make parameter sniffing less of a problem for customers, so I hope this gives you insight in the meantime to work around the issue for your scenario.