For small tasks you can use Bayesian Q-Learning https://ocs.aaai.org/Papers/AAAI/1998/AAAI98-108.pdfBayesian Q-Learning.
For larger tasks, you can use its variational version https://pdfs.semanticscholar.org/ce2e/0bd9135814f4018106bc31d87902b358e251.pdfvariational version.
The core idea is to systematically try suboptimal x
which shall pay off in the long term.