Firstly, I would suggest you do not use softmax for exploration, because it does not imply the model's uncertainty. Training with softmax and cross-entropy, your model may be very confident, but wrongly, because of overfitting.
Another reason why you should not use softmax to measure uncertainty is that your estimate of the variance (optimal estimate of the variance is the average error) may be quite low, explaining the low entropy of your model. However, there maybe exist regions (holes), where your model is highly uncertain (large error).
Thus, you should try other options for measuring uncertainty.
One way to measure model (or epistemic) uncertainty is to use a Bayesian Network estimating the whole distribution $p(\theta | D)$, where \theta are your parameters and D is the collected dataset of experience. The entropy of $p(\theta | D)$ tells us the model uncertainty.
Why Bayesian Network? Intuitively, if our estimator says all θs are equally likely given your data, then it means that you have no idea of what the model really is. On the other hand, if it says there is one only θ, that can possibly explain D, then you have high confidence in the model.
Another way to measure epistemic uncertainty is to use bootstrap ensembling. Instead of estimating the uncertainty of every single parameter in the Bayesian Net, learn N different networks! Use bootstrapping in order to generate N datasets (of same size as D) by resampling with replacement. Then train each network on a corresponding generated dataset. Then in testing, you can either sample uniformly a network ($p(\theta | D) = \frac{1}{N}\sum_i^N{\delta({\theta}_i)}$) or just average all networks predictions.
For exploration (in Deep RL), there are a lot of different options. I recommend you check information gain, Thompson sampling and pseudo-counts. However, if you were using the standard deep RL agents, like DQN etc, you could begin with the standard ε-greedy behavior policy, ignoring that this is not an optimal exploration policy for the most cases.