New Directions in Bandit Learning: Singularities and Random Walk Feedback