We explore the interaction between information sampling and the structure of the social environment in the case of two prominent social learning strategies: imitate-the-best and imitate-the-majority. In a series of simulations a group of agents made repeated choices between options. We varied the building blocks of the strategies used by agents, the structure of the social network and characteristics of the task environment. A key factor influencing strategies’ success is the speed with which they are able to respond to environmental change. In general, imitate-the-best provides a faster response compared to imitate-the-majority and larger samples help the former but hurt the latter. Less efficient networks decrease the performance of both, but are more detrimental for imitate-the-majority. Our findings highlight the role of sampling and social structure in the study of social learning, an area not sufficiently explored before.