This thesis is focused on the development of sample-efficient algorithms for personalized data-driven decision-making. In particular, the dissertation aims to address the following questions in both online (sequential) and offline (batch) settings: (i) What problem structures allow for achieving instance-specific fast regret rates? (ii) How can these problem structures be leveraged to design \textit{practical} algorithms that achieve fast theoretical rates? Part I of this thesis investigates the above questions from an online perspective. Chapter 2 studies the smooth contextual bandit problem, where we use the smoothness property of the function class to design contextual bandit algorithms that interpolate between two extremes previously studied in isolation: nondifferentiable bandits and parametric-response bandits. Chapter 3 examines the DTR bandit problem, where we develop the first online algorithm with logarithmic regret for dynamic treatment regimes that involve personalized, adaptive, multi-stage treatment plans. Part II of this work delves into fast regret rates for offline problems by leveraging a probabilistic condition that measures the distribution of the reward gap between the optimal and second-optimal decisions, which we term the margin condition. In the case of contextual linear optimization, Chapter 4 shows that the naive plug-in approach actually achieves regret convergence rates that are significantly faster than methods that directly optimize downstream decision performance. In the case of offline reinforcement learning, Chapter 5 presents a finer regret analysis that characterizes the faster-than-square-root regret convergence rate we observe in practice.