The apt path you describe shows that libcuda1-396 depends on nvidia-396, but that does not necessarily mean that you’ll get libcuda1-396 when you install nvidia-396.
On my system, the nvidia-396 package “recommends” libcuda1-396, but does not install it by default because the nvidia-396 package does not “require” it. This is on Linux Mint 18.3. I believe this situation is consistent also with the listing you provided.
However, this does indicate that it should work to explicitly install the libcuda1-396 package, with
apt-get install libcuda1-396
and indeed that gets you a better version of cuda than what I tried before.
(For completeness, I used the “-410” variants and not “-396” but it probably doesn’t matter and I wanted to keep the example the same.)
So, to summarize, on my system, at least, I updated the nvidia driver, and also the recommended external cuda (required by pytorch for peripheral purposes) using the following commands, and that made it work for me:
sudo apt-get install nvidia-410
sudo apt-get install libcuda1-410
It is a little unfortunate that pytorch is almost, but not quite, independent of the system-installed cuda. It packages its own, but still needs an external one. This makes fastai have the same dependency. This is unfortunate, because there are potentially other clients of cuda that might have their own requirements for the system-installed cuda. For example, doing the above broke my working TensorFlow setup. I’ll rebuild TensorFlow and can fix it, but this is an example of fastai (via pytorch) being not quite self-contained. I think for the final 1.0 version of the library it would be much better if it were.