Answer Set Programming (ASP) is a well-known problem solving approach based on non-monotonic logic programs and efficient solvers. To enable access to external information, HEX-programs extend programs with external atoms, which allow for a bidirectional communication between the logic program and external sources of computation (e.g., description logic reasoners and Web resources). Current solvers evaluate HEX-programs by a translation to ASP itself, in which values of external atoms are guessed and verified after the ordinary answer set computation. This elegant approach does not scale with the number of external accesses in general, in particular in presence of non-determinism (which is instrumental for ASP). In this paper, the authors present a novel, native algorithm for evaluating HEX-programs which uses learning techniques.