Characterizing the level of primordial non-Gaussianity (PNG) in the initial
conditions for structure formation is one of the most promising ways to test
inflation and differentiate among different scenarios. The scale-dependent
imprint of PNG on the large-scale clustering of galaxies and quasars has
already been used to place significant constraints on the level of PNG in our
observed Universe. Such measurements depend upon an accurate and robust theory
of how PNG affects the bias of galactic halos relative to the underlying matter
density field. We improve upon previous work by employing a more general
analytical method - the path-integral extension of the excursion set formalism
- which is able to account for the non-Markovianity caused by PNG in the
random-walk model used to identify halos in the initial density field. This
non-Markovianity encodes information about environmental effects on halo
formation which have so far not been taken into account in analytical bias
calculations. We compute both scale-dependent and -independent corrections to
the halo bias, along the way presenting an expression for the conditional
collapsed fraction for the first time, and a new expression for the conditional
halo mass function. To leading order in our perturbative calculation, we
recover the halo bias results of Desjacques et. al. (2011), including the new
scale-dependent correction reported there. However, we show that the
non-Markovian dynamics from PNG can lead to marked differences in halo bias
when next-to-leading order terms are included. We quantify these differences
here. [abridged]