How do you initialize the expected rewards for all arms? In other words, in the very first iteration, when you have not made any observations at all yet, what reward does your algorithm expect to receive from each arm?
If your answer currently is to initialize everything to $0$ (which is probably the case if you didn't explicitly think about it), I'd recommend initializing everything to something more optimistic (for example, initializing all expected rewards to $1$ when you have no observations yet for an arm.
Why would this help? Consider the following easy example: we have three arms. The first arm gives a reward around $0.1$, the second around $0.5$, and the third around $0.9$. In the very first iteration, you don't have any observations, so you'll just randomly pick an arm. Suppose you initialized all expected rewards to $0$, and you random picked the second arm. This lets you observe rewards for the first two arms, for which you'll update your expectations towards $0.1$ and $0.5$. You don't observe any reward for the third arm, so that one will stay at the expected value you initialized ($0$). In your second iteration, it will be much more likely to pick arm two again, because it has the highest expected reward. If you had instead initialized all arms to an expected reward of $1$, you'd be very likely to pick the third arm in your second iteration.
This kind of optimistic initialization is almost always useful, in any kind of Multi-Armed Bandit problem. Apart from that, I suspect it may also be beneficial in your specific case to update all arms every iteration, not only the ones for which you made observations. Suppose you played an arm and observed a reward $r$. You described that you can already also observe the rewards of all other arms with rewards $< r$, and update those with the correct rewards. This actually also gives you some information about all the remaining arms, the ones with rewards $> r$, and you do not use this information to update those yet.
Now, you don't have precise information for them, you don't know exactly how much higher than $r$ they would be, but you do know that they would all have a reward of at least $r$. So, I suspect it would be useful to simply update all of those by pretending they had a reward of $r$. Alternatively, it may be worth trying to update them all with a reward of $r + \alpha$ for some small value $\alpha$, but I'm not 100% sure about that; you'd have to evaluate it empirically.